Name
Abstract | ||
|---|---|---|
A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different lp norms. We address this problem by introducing the concept of an all-norm p-approximation algorithm, which supplies one solution that guarantees p-approximation to all lp norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259-271] showed a 2-approximation algorithm for the problem with respect to the l∞ norm. For any fixed lp norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given lp norm (p 1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given lp norm a FPTAS for any fixed number of machines. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.jalgor.2004.02.003 | Scandinavian Workshop on Algorithm Theory |
Keywords | Field | DocType |
all-norm p-approximation algorithm,fixed lp norm,all-norm approximation algorithm,different optimal solution,optimization problem,2-approximation algorithm,different lp norm,lp norm,restricted assignment problem,approximation algorithm,2-approximation polynomial algorithm,scheduling problem,assignment problem | Approximation algorithm,Discrete mathematics,Combinatorics,Scheduling (computing),Lp space,Norm (social),Assignment problem,Binary search algorithm,Optimization problem,Mathematics,Polynomial-time approximation scheme | Journal |
Volume | Issue | ISSN |
52 | 2 | 0196-6774 |
ISBN | Citations | PageRank |
3-540-43866-1 | 28 | 1.15 |
References | Authors | |
16 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yossi Azar | 1 | 3330 | 365.24 |
| Leah Epstein | 2 | 1163 | 104.95 |
| Yossi Richter | 3 | 207 | 11.38 |
| Gerhard Woeginger | 4 | 4176 | 384.37 |
| GJ Woeginger | 5 | 77 | 4.15 |