Name
Abstract | ||
|---|---|---|
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 [13]. We first show that the problem is hard and that there is no constant ratio polynomial approximation unless P = NP 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 simulations are finally reported using a benchmark of instances on SAT solvers. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/IPDPS.2009.5160879 | IPDPS |
Keywords | Field | DocType |
parallel processing,polynomial approximation,resource allocation,SAT solvers,approximation ratio,constant ratio polynomial approximation,good combination,homogeneous discrete resources,multiple heuristics,parallel resources,portfolio problem,resource allocation | Resource management,Approximation algorithm,Mathematical optimization,Heuristic,Polynomial,Computer science,Oracle,Heuristics,Schedule,Resource allocation | Conference |
ISSN | Citations | PageRank |
1530-2075 | 7 | 0.60 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marin Bougeret | 1 | 113 | 13.35 |
| Pierre-françois Dutot | 2 | 166 | 13.95 |
| Alfredo Goldman | 3 | 7 | 0.60 |
| Yanik Ngoko | 4 | 56 | 11.68 |
| Denis Trystram | 5 | 1120 | 160.57 |