All-norm approximation algorithms

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 l(p) norms. We address this problem by introducing the concept of an all-norm p-approximation algorithm, which supplies one solution that guarantees to-approximation to all et, norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are in 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 linfinity norm. For any fixed l(p) norm the previously known approximation algorithm has a performance of 0(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 l(p) norm (p > 1) there is no PTAS unless P = NP by showing an APX-hardness result. We also show for any given l(p) norm a FPTAS for any fixed number of machines. (C) 2004 Elsevier Inc. All rights reserved.