2026-07-23T20:16:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3330 2024-03-06T10:34:06Z ddc:004 open_access

The Semi-stochastic Ski-rental Problem Madry, Aleksander Panigrahi, Debmalya online optimization stochastic algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksander Madry and Debmalya Panigrahi 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.300 urn:nbn:de:0030-drops-33305 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.300 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode