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.
2008
19th Annual ACM-SIAM Symposium on Discrete Algorithms
Case analysis; Input sequence; Lower bounds
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
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).
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/367561
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 50
  • ???jsp.display-item.citation.isi??? 38
social impact