License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.300
URN: urn:nbn:de:0030-drops-33305
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3330/
Go to the corresponding LIPIcs Volume Portal

Madry, Aleksander ; Panigrahi, Debmalya

The Semi-stochastic Ski-rental Problem

pdf-format:
12.pdf (0.4 MB)

Abstract

In this paper, we introduce the semi-stochastic model for dealing with input uncertainty in optimization problems. This model is a hybrid between the overly pessimistic online model and the highly optimistic stochastic (or Bayesian) model. In this model, the algorithm can obtain only limited stochastic information about the future (i.e. about the input distribution)---as the amount of stochastic information we make available to the algorithm grows from no information to full information, we interpolate between the online and stochastic models. The central question in this framework is the trade-off between the performance of an algorithm, and the stochastic information that it can access. As a first step towards understanding this trade-off, we consider the ski-rental problem in the semi-stochastic setting. More precisely, given a desired competitive ratio, we give upper and lower bounds on the amount of stochastic information required by a deterministic algorithm for the ski-rental problem to achieve that competitive ratio.

BibTeX - Entry

@InProceedings{madry_et_al:LIPIcs:2011:3330,
  author =	{Aleksander Madry and Debmalya Panigrahi},
  title =	{{The Semi-stochastic Ski-rental Problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{300--311},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3330},
  URN =		{urn:nbn:de:0030-drops-33305},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.300},
  annote =	{Keywords: online optimization, stochastic algorithm}
}

Keywords: online optimization, stochastic algorithm
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI