Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Approximation Scheme
Polynomial Approximation
Sat Solver
Subscribe
Academic
Publications
Combining multiple heuristics on discrete resources
Combining multiple heuristics on discrete resources,10.1109/IPDPS.2009.5160879,Marin Bougeret,Pierrefrançois Dutot,Alfredo Goldman,Yanik Ngoko,Denis
Edit
Combining multiple heuristics on discrete resources
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Marin Bougeret
,
Pierrefrançois Dutot
,
Alfredo Goldman
,
Yanik Ngoko
,
Denis Trystram
In this work we study the portfolio problem which is to find a good combination of multiple heuristics to solve given instances on parallel resources in minimum time. The resources are assumed to be discrete, it is not possible to allocate a resource to more than one heuristic. Our goal is to minimize the average completion time of the set of instances, given a set of heuristics on homogeneous discrete resources. This problem has been studied in the continuous case in (18). We first show that the problem is hard and that there is no constant ratio
polynomial approximation
in the general case. Then, we design several approximation schemes for a restricted version of the problem where each heuristic must be used at least once. These results are obtained by using oracle with several guesses, leading to various tradeoff between the size of required information and the approximation ratio. Some additional results based on experiments are finally reported using a benchmark of instances on SAT solvers.
Conference:
International Parallel and Distributed Processing Symposium/International Parallel Processing Symposium  IPDPS(IPPS)
, pp. 18, 2009
DOI:
10.1109/IPDPS.2009.5160879
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
www.integrade.org.br
)
(
dx.doi.org
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(1)
...In the first approach, we improve a problem introduced in [7,
4
] such as to reduce the number of unsolved SAT instances...
...This problem can be informally recalled as follows: given a set of opportunities, an amount of possible investments on the set of opportunities and the payoff obtained when investing an amount on each opportunity, what is the best amount of investment to make on each opportunity in order to maximize the sum of the payoffs? This scheme can be adapted to algorithms using the algorithm portfolio approach [2, 1, 7,
4
]. A portfolio of ...
...Morever the interest to allocate for every instance to solve the adequate resources on more than one algorithm is that we may not know which is the best suited SAT solver for each instance before actually solving it. Our proposed approaches aim at improving those introduced in [7,
4
] from the observation that they do not focus on the necessity to provide an answer for all the considered instances...
...In [7, 3,
4
] the authors study how resources can be shared for SAT solvers such as to efficiently solve instances closed to those of a predefined benchmark...
...The first model has been suggested in [
4
] and is based on a general problem (discrete Resource Sharing Scheduling Problem, dRSSP) that we improve for the case of SAT...
...In Section 3, we consider the CBALapproach when there exists a benchmark of instances and propose an algorithm based on the discrete Resource Sharing Problem (dRSSP) introduced in [
4
]...
...Given a set of algorithms A and a set of instances I, one interesting property here is that the optimal solution using the CBALis always at least as good as the best algorithm a opt ∈A executed on the set of instances in I. A particular case using the CBAL approach consists in considering the MA (Mean Allocation) algorithm [
4
] which given a resource decomposition m = qk + r (where 0 ≤ r<k ) allocates q +1 resources to r algorithms ai, 1 ...
...The first model is based on thedRSSP problem presented in [
4
]...
...Theorem 3.1. dRSSP with linear cost assumption is NPComplete and it is not approximable unless P = NP [
4
]...
...We refer the reader to [
4
] for the details...
...In [
4
], many approximation schemes are provided for dRSSP using an oracle based approach...
...MA G2 (x) proposed in [
4
] to solve dRSSP .G ivenk candidate algorithms and a value x, this scheme produces a k/xapproximation of the optimal solution where each candidate algorithm has at least one resource...
...The first model extends the dRSSP introduced in [
4
] to combine in such a way to take into account the cutoff time...
Yanik Ngoko
,
et al.
Combining SAT solvers on discrete resources
References
(18)
On the Influence of Lookahead in Competitive Paging Algorithms
(
Citations: 45
)
Susanne Albers
Journal:
Algorithmica
, vol. 18, no. 3, pp. 283305, 1997
Distributed Computing with Advice: Information Sensitivity of Graph Coloring
(
Citations: 20
)
Pierre Fraigniaud
,
Cyril Gavoille
,
David Ilcinkas
,
Andrzej Pelc
Conference:
International Colloquium on Automata, Languages and Programming  ICALP
, pp. 231242, 2007
Boosting Stochastic Problem Solvers Through Online SelfAnalysis of Performance
(
Citations: 11
)
Vincent A. Cicirello
Published in 2003.
Selfadapting numerical software (SANS) effort
(
Citations: 15
)
Jack Dongarra
,
George Bosilca
,
Zizhong Chen
,
Victor Eijkhout
,
Graham E. Fagg
,
Erika Fuentes
,
Julien Langou
,
Piotr Luszczek
,
Jelena Pjesivacgrbovic
,
Keith Seymour
,
Haihang You
,
Sathish S. Vadhiyar
Journal:
Ibm Journal of Research and Development  IBMRD
, vol. 50, no. 23, pp. 223238, 2006
Computers and Intractability: A Guide to the Theory of NPCompleteness
(
Citations: 19196
)
Michael Randolph Garey
,
David S. Johnson
Conference:
Artificial Evolution  AE
, 1979
Sort by:
Citations
(1)
Combining SAT solvers on discrete resources
Yanik Ngoko
,
Denis Trystram
Conference:
International Conference on High Performance Computing & Simulation  HPCS
, 2009