(Incremental) priority algorithms

ABSTRACT

We study the question of what optimization problems can be optimally or approximately solved by "greedy-like" algorithms. For definiteness, we will limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for "greedy-like" algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we will provide a precise definition of what we mean by greedy and greedy-like. A full version of this paper is available at http://www.cs.toronto.edu/~ bor/priority.ps.

REFERENCES

• 1: E. M. Arkin , E. B. Silverberg, Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, v.18 n.1, p.1-8, Nov. 1987 [doi>10.1016/0166-218X(87)90037-0]
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 3: Yossi Azar , Joseph Seffi Naor , Raphael Rom, The competitiveness of on-line assignments, Journal of Algorithms, v.18 n.2, p.221-237, March 1995 [doi>10.1006/jagm.1995.1008]
• 4: Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Approximating the throughput of multiple machines under real-time scheduling, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.622-631, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301420]
• 5: S. Baruah , G. Koren , B. Mishra , A. Raghunathan , L. Rosier , D. Shasha, On-line scheduling in the presence of overload, Proceedings of the 32nd annual symposium on Foundations of computer science, p.100-110, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185354]
• 6: Gilles Brassard and Paul Bratley. Introduction to Algorithms, chapter 6. Prentice Hall, Englewood Cliffs, New Jersey., 1996.
• 7: Martin C. Carlisle , Errol L. Lloyd, On the k-Coloring of Intervals, Proceedings of the International Conference on Computing and Information: Advances in Computing and Information, p.90-101, May 27-29, 1991
• 8: Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258657]
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: 2nd Twente workshop on Graphs and combinatorial optimization, June 1994
• 11: M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman, New York City, New York., 1996.
• 12: T. E. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985.
• 13: R. L. Graham. Bounds for Certain Multiprocessing Anomalies. Bell Systems Technical Journal, 45:1563-1581, 1966.
• 14: R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(1):416-429, March 1969.
• 15: R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Mathematics, 5:287-326, 1979.
• 16: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 17: Gilad Koren , Dennis Shasha, MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling, Theoretical Computer Science, v.128 n.1-2, p.75-97, June 6, 1994 [doi>10.1016/0304-3975(94)90165-1]
• 18: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. Zipkin, editors, Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory. North-Holland, Amsterdam, 1993.
• 19: Stefano Leonardi , Alberto Marchetti-Spaccamela , Alessio Presciutti , Adi Rosén, On-line randomized call control revisited, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.323-332, January 25-27, 1998, San Francisco, California, United States
• 20: Bernard M. E. Moret , Henry D. Shapiro, Algorithms from P to NP (vol. 1): design and efficiency, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 21: Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976 [doi>10.1145/321921.321934]
• 22: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 23: Steve Sieden, Jiri Sgall, and Gerhard Woeginger. Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27(5):215-221, 2000.