(1) School of Computer Science, The Interdisciplinary Center, Herzliya, Israel;(2) Mathematical Institute, AS CR, Zitná 25, CZ-11567 Praha 1, Czech Republic
Abstract:
We give a polynomial approximation scheme for the problem of
scheduling on uniformly related parallel machines for a large
class of objective functions that depend only on the machine
completion times, including minimizing the lp norm of the
vector of completion times. This generalizes and simplifies
many previous results in this area.