|
 ABSTRACT
The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each &egr;, an algorithm that runs in time O((n/&egr;)1/&egr;2) and has relative error at most &egr; is given. In addition, more practical algorithms for &egr; = 1/5 + 2-k and &egr; = 1/6 + 2-k, which have running times O(n(k + log n)) and O(n(km4 + log n)) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously.
The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
COFFMAN, JR, E. G., GAREY, M. R., AND JOHNSON, D. S. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7 (1978), 1-17.
|
| |
2
|
FERNANDEZ DE Lk VEGA, W., AND LUEKER, G.S. Bin packing can be solved within 1 + ~ in linear time. Combinatorica I (1981), 349-355.
|
| |
3
|
FRIESEN, D. K. Sensitivity analysis for heuristic algorithms. Tech. Rep. UIUCDCS-R-78-939, Department of Computer Science, Univ. of Illinois, Urbana-Champaign, 1978.
|
| |
4
|
FRIESEN, D.K. Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput. 13 (1984), 170-181.
|
| |
5
|
|
| |
6
|
GRAHAM, R. L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45 (1966), 1563-1581.
|
| |
7
|
GRAHAM, R.L. Bounds on multiprocessing timing anomalies. SIAM J~ Appl. Math. 17 (1969), 263-269.
|
| |
8
|
|
 |
9
|
|
| |
10
|
KARMARKAR, N., AND KARP, R.M. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 312-320.
|
| |
11
|
|
| |
12
|
LAWLER, E.L. Fast approximation algorithms for knapsack problems. In Proceedings of the 18th IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1977, pp. 206-213.
|
| |
13
|
|
CITED BY 65
|
|
Mark Scharbrodt , Angelika Steger , Horst Weisser, Approximability of scheduling with fixed jobs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.961-962, January 17-19, 1999, Baltimore, Maryland, United States
|
|
|
Esther M. Arkin , Michael A. Bender , Sándor P. Fekete , Joseph S. B. Mitchell , Martin Skutella, The freeze-tag problem: how to wake up a swarm of robots, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.568-577, January 06-08, 2002, San Francisco, California
|
|
|
|
|
|
Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating bandwidth for bursty connections, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.664-673, May 04-06, 1997, El Paso, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
Noga Alon , Yossi Azar , Gerhard J. Woeginger , Tal Yadid, Approximation schemes for scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.493-500, January 05-07, 1997, New Orleans, Louisiana, United States
|
|
|
James B. Orlin , Andreas S. Schulz , Sudipta Sengupta, &egr;-optimization schemes and L-bit precision (extended abstract): alternative perspectives in combinatorial optimization, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.565-572, May 21-23, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
Soumen Chakrabarti , James Demmel , Katherine Yelick, Modeling the benefits of mixed data and task parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.74-83, June 24-26, 1995, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
E. G. Coffman, Jr. , George S. Lueker, Approximation algorithms for extensible bin packing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.586-588, January 07-09, 2001, Washington, D.C., United States
|
|
|
|
|
|
|
|
|
R. J. Lipton , E. Markakis , E. Mossel , A. Saberi, On approximately fair allocations of indivisible goods, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bogdan Caprita , Jason Nieh , Clifford Stein, Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Qunfeng Dong , Ashutosh Shukla , Vivek Shrivastava , Dheeraj Agrawal , Suman Banerjee , Koushik Kar, Load balancing in large-scale RFID systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.9, p.1782-1796, June, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2