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.
Stochastic analyses for online combinatorial optimization problems / Garg, N; Gupta, A; Leonardi, Stefano; Sankowski, Piotr. - (2008), pp. 942-951. (Intervento presentato al convegno 19th Annual ACM-SIAM Symposium on Discrete Algorithms tenutosi a San Francisco; United States nel January 2008).
Stochastic analyses for online combinatorial optimization problems.
LEONARDI, Stefano;SANKOWSKI, PIOTR
2008
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 ω[A(ω)/OPT(ω)]. Finally, we use these ideas to give an average-case analysis of the Universal TSP problem.File | Dimensione | Formato | |
---|---|---|---|
VE_2008_11573-367561.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
506.23 kB
Formato
Adobe PDF
|
506.23 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.