SIGACT news online algorithms column 10: competitiveness via doubling

ABSTRACT

We discuss what we refer to, tentatively, as the "doubling" method for designing online and offline approximation algorithms. The rough idea is to use geometrically increasing estimates on the optimal solution to produce fragments of the algorithm's solution. The term "doubling" is a little misleading, for often factors other than 2 are used, and suggestions for a better name will be appreciated.

REFERENCES

• 1: Edward J. Anderson , Chris N. Potts, Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time, Mathematics of Operations Research, v.29 n.3, p.686-697, August 2004 [doi>10.1287/moor.1040.0092]
• 2: A. Archer, R. Rajagopalan, and D. Shmoys. Lagrangian relaxation for the k-median problem: new insights and continuity properties. In Proc. 11th European Symp. on Algorithms (ESA), pages 31--42, 2003.
• 3: 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]
• 4: Ricardo A. Baeza-Yates , Joseph C. Culberson , Gregory J. E. Rawlins, Searching in the plane, Information and Computation, v.106 n.2, p.234-252, Oct. 1993 [doi>10.1006/inco.1993.1054]
• 5: A. Bar-Noy, A. Freund, and J. Naor. New algorithms for related machines with temporary jobs. J. Sched., 3:259--272, 2000.
• 6: A. Beck. On the linear search problem. Naval Research Logistics Quarterly, 2:221--228, 1964.
• 7: R. Bellman. An optimal search problem. SIAM Review, 5:274, 1963.
• 8: Piotr Berman , Moses Charikar , Marek Karpinski, On-line load balancing for related machines, Journal of Algorithms, v.35 n.1, p.108-121, April 2000 [doi>10.1006/jagm.1999.1070]
• 9: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 10: Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237577]
• 11: Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
• 12: 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]
• 13: Kamalika Chaudhuri , Brighten Godfrey , Satish Rao , Kunal Talwar, Paths, Trees, and Minimum Latency Tours, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.36, October 11-14, 2003
• 14: C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
• 15: M. Chrobak, C. Kenyon, J. Noga, and N. Young. Online medians via online bidding. In Proc. 7th Latin American Theoretical Informatics Symp. (LATIN), volume 3887 of Lecture Notes in Comput. Sci., pages 311--322, 2006.
• 16: Fabián A. Chudak , David B. Shmoys, Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, Journal of Algorithms, v.30 n.2, p.323-343, Feb. 1999 [doi>10.1006/jagm.1998.0987]
• 17: A. Das and C. Kenyon. On hierarchical diameter-clustering and the supplier problems. In Proc. WAOA'06, 4th Workshop on Approximation and Online Algorithms, September 2006, Zurich, Switzerland, LNCS, Springer, 2006.
• 18: Sanjoy Dasgupta , Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences, v.70 n.4, p.555-569, June 2005 [doi>10.1016/j.jcss.2004.10.006]
• 19: E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost, 2004.
• 20: T. Ebenlendr and J. Sgall. Optimal and online preemptive scheduling on uniformly related machines. In Proc. 21st Symp. on Theoretical Aspects of Computer Science (STACS), volume 2996 of Lecture Notes in Comput. Sci., pages 199--210. Springer, 2004.
• 21: T. Ebenlendr, J. Sgall, and W. Jawor. Preemptive online scheduling: Optimal algorithms for all speeds. In Proc. 13th European Symp. on Algorithms (ESA), volume 4168 of Lecture Notes in Comput. Sci., pages 327--339. Springer, 2006.
• 22: S. Gal. Search Games. Academic Press, 1980.
• 23: Michel Goemans , Jon Kleinberg, An improved approximation ratio for the minimum latency problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.152-158, January 28-30, 1996, Atlanta, Georgia, United States
• 24: M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111--124, 1998.
• 25: T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Comput. Sci., 38:293--306, 1985.
• 26: R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical J., 45:1563--1581, 1966.
• 27: 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
• 28: Leslie A. Hall , Andreas S. Schulz , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, v.22 n.3, p.513-544, Aug. 1997 [doi>10.1287/moor.22.3.513]
• 29: Han Hoogeveen , Arjen P. A. Vestjens, Optimal On-Line Algorithms for Single-Machine Scheduling, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.404-414, June 03-05, 1996
• 30: Ming-Yang Kao , John H. Reif , Stephen R. Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.441-447, January 25-27, 1993, Austin, Texas, United States
• 31: Guolong Lin , Chandrashekhar Nagarajan , Rajmohan Rajaraman , David P. Williamson, A general approach for incremental approximation and hierarchical clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1147-1156, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109684]
• 32: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 33: Ramgopal R. Mettu , C. Greg Plaxton, The Online Median Problem, SIAM Journal on Computing, v.32 n.3, p.816-832, 2003 [doi>10.1137/S0097539701383443]
• 34: Rajeev Motwani , Steven Phillips , Eric Torng, Non-clairvoyant scheduling, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.422-431, January 25-27, 1993, Austin, Texas, United States
• 35: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 36: Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
• 37: René Sitters, The Minimum Latency Problem Is NP-Hard for Weighted Trees, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.230-239, May 27-29, 2002