Approximation schemes for scheduling

Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid

Research output: Contribution to conferencePaper

77 Scopus citations

Abstract

We consider the classic scheduling/load balancing problems where there are m identical machines and n jobs, and each job should be assigned to some machine. Traditionally, the assignment of jobs to machines is measured by the makespan (maximum load) i.e., the L norm of the assignment. An ε-approximation scheme was given by Hochbaum and Shmoys for minimizing the L norm. In several applications, such as in storage allocation, a more appropriate measure is the sum of the squares of the loads (which is equivalent to the L2 norm). This problem was considered in [4, 5, 13] who showed how to approximate the optimum value by a factor of about 1.04. In fact, a more general measure, which is the Lp norm (for any p≥1) can also be approximated to some constant which may be as large as 3/2. We improve these results by providing an ε-approximation scheme for the general Lp norm (and in particular for the L2 norm). We also consider the case of restricted assignment of unit jobs where we show how to find in polynomial time, a solution which is optimal for all norms.

Original languageEnglish (US)
Pages493-500
Number of pages8
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximation schemes for scheduling'. Together they form a unique fingerprint.

Cite this