TY - GEN

T1 - Stochastic analyses for online combinatorial optimization problems

AU - Garg, Naveen

AU - Gupta, Anupam

AU - Leonardi, Stefano

AU - Sankowski, Piotr

PY - 2008

Y1 - 2008

N2 - 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 ω[A(ω)/OPT(ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.

AB - 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 ω[A(ω)/OPT(ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.

UR - http://www.scopus.com/inward/record.url?scp=57949102377&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57949102377&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:57949102377

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 942

EP - 951

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -