# All-norm approximation algorithms

Azar, Yossi
and
Epstein, Leah
and
Richter, Yossi
and
Woeginger, Gerhard J.
(2004)
*All-norm approximation algorithms.*
Journal of Algorithms, 52
(2).
pp. 120-133.
ISSN 0196-6774

PDF
Restricted to UT campus only : Request a copy 227kB |

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 ℓp norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓp 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 ℓ∞ norm. For any fixed ℓp 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 ℓp norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓp norm a FPTAS for any fixed number of machines. |

Item Type: | Article |

Copyright: | © 2004 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/76271 |

Official URL: | http://dx.doi.org/10.1016/j.jalgor.2004.02.003 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 219744