Stochastic analyses for online combinatorial optimization problems

ABSTRACT

In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online problems like paging and k-server, it is not known how to beat the Φ(log n) bound for online Steiner tree if at each time instant, the demand vertex is a uniformly random vertex from the graph. For the online Steiner tree problem, we show that if each demand vertex is an independent draw from some probability distribution π: V → [0, 1], a variant of the natural greedy algorithm achieves E_ω[A(ω)]/E_ω[OPT (ω)] = O(1); moreover, this result can be extended to some other subadditive problems. Both assumptions that the input sequence consists of independent draws from π, and that π is known to the algorithm are both essential; we show (almost) logarithmic lower bounds if either assumption is violated. Moreover, we give preliminary results on extending the Steiner tree results above to the related "expected ratio" measure E_ω[ω(ω)/OPT (ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.

REFERENCES

• 1: Susanne Albers. Online algorithms: a survey. Math. Program., 97(1--2, Ser. B):3--26, 2003. ISMP, 2003 (Copenhagen).
• 2: Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999 [doi>10.1145/333580.333583]
• 3: Noga Alon and Yossi Azar. On-line Steiner trees in the Euclidean plane. Discrete Comput. Geom., 10(2):113--121, 1993.
• 4: Luca Becchetti. Modelling locality: a probabilistic analysis of LRU and FWF. In Algorithms---ESA 2004, volume 3221 of Lecture Notes in Comput. Sci., pages 98--109. Springer, Berlin, 2004.
• 5: S. Ben-David and A. Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11(1):73--91, 1994.
• 6: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 7: Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
• 8: Moses Charikar, Chandra Chekuri, and Martin Pál. Sampling bounds for stochastic optimization. In Approximation, randomization and combinatorial optimization, volume 3624 of Lecture Notes in Comput. Sci., pages 257--269. Springer, Berlin, 2005.
• 9: Andrew Chou , Jeremy Cooperstock , Ran El-Yaniv , Michael Klugerman , Tom Leighton, The statistical adversary allows optimal money-making trading strategies, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.467-476, January 22-24, 1995, San Francisco, California, United States
• 10: F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schäfer. A tighter analysis of random sampling for connected facility location. Submitted, 2007.
• 11: Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225280]
• 12: Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
• 13: Amos Fiat and Gerhard J. Woeginger, editors. Online algorithms, volume 1442 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1998. The state of the art, Papers from the Workshop on the Competitive Analysis of On-line Algorithms held in Schloss Dagstuhl, June 1996.
• 14: Lisa Fleischer , Jochen Könemann , Stefano Leonardi , Guido Schäfer, Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132609]
• 15: Dimitris Fotakis. On the competitive ratio for online facility location. In Automata, languages and programming, volume 2719 of Lecture Notes in Comput. Sci., pages 637--652. Springer, Berlin, 2003.
• 16: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 17: Anupam Gupta , Amit Kumar , Martin Pál , Tim Roughgarden, Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.606, October 11-14, 2003
• 18: Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780597]
• 19: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 20: Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369--384, 1991.
• 21: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 22: Sandy Irani and Anna R. Karlin. On online computation. In Dorit Hochbaum, editor, Approximation Algorithms for NP Hard Problems. PWS publishing Co, 1996.
• 23: Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly Competitive Algorithms for Paging with Locality of Reference, SIAM Journal on Computing, v.25 n.3, p.477-497, June 1996 [doi>10.1137/S0097539792236353]
• 24: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 25: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 26: Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79--119, 1988.
• 27: Anna R. Karlin , Steven J. Phillips , Prabhakar Raghavan, Markov Paging, SIAM Journal on Computing, v.30 n.3, p.906-922, 2000 [doi>10.1137/S0097539794268042]
• 28: Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning and shortest path trees. Algorithmica, 14(4):305--322, 1995.
• 29: Elias Koutsoupias , Christos H. Papadimitriou, Beyond Competitive Analysis, SIAM Journal on Computing, v.30 n.1, p.300-317, 2000 [doi>10.1137/S0097539796299540]
• 30: Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
• 31: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001
• 32: A. Meyerson, Designing Networks Incrementally, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.406, October 14-17, 2001
• 33: Konstantinos Panagiotou , Alexander Souza, On adequate performance measures for paging, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132587]
• 34: C. A. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. Algorithmica, 32(2):163--200, 2002.
• 35: Prabhakar Raghavan. A statistical adversary for online algorithms. In Online Algorithms, volume 53 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 79--83. Amer. Math. Soc., Providence, RI, 1991.
• 36: R. Ravi and Amitabh Sinha. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In Proceedings of the 10th Integer Programming and Combinatorial Optimization Conference (IPCO), pages 101--115, 2004.
• 37: Gabriel Robins , Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation, SIAM Journal on Discrete Mathematics, v.19 n.1, p.122-134, 2005 [doi>10.1137/S0895480101393155]
• 38: Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput., 6(3):563--581, 1977.
• 39: Mark Scharbrodt , Thomas Schickinger , Angelika Steger, A new average case analysis for completion time scheduling, Journal of the ACM (JACM), v.53 n.1, p.121-146, January 2006 [doi>10.1145/1120582.1120585]
• 40: David B. Shmoys , Chaitanya Swamy, An approximation scheme for stochastic linear programming and its application to stochastic integer programs, Journal of the ACM (JACM), v.53 n.6, p.978-1012, November 2006 [doi>10.1145/1217856.1217860]
• 41: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 42: Alexander Souza and Angelika Steger. The expected competitive ratio for weighted completion time scheduling. Theory Comput. Syst., 39(1):121--136, 2006.
• 43: Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
• 44: Neal E. Young, On-line paging against adversarially biased random inputs, Journal of Algorithms, v.37 n.1, p.218-235, Oct. 2000 [doi>10.1006/jagm.2000.1099 ]