License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.4
URN: urn:nbn:de:0030-drops-112196
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11219/
Go to the corresponding LIPIcs Volume Portal

Hershkowitz, David Ellis ; Ravi, R. ; Singla, Sahil

Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty

pdf-format:
LIPIcs-APPROX-RANDOM-2019-4.pdf (0.6 MB)

Abstract

In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we introduce the MinEMax model to study "build versus rent" problems. In our model different scenarios appear independently. Before knowing which scenarios appear, we may build rigid resources that cannot be changed for different scenarios. Once we know which scenarios appear, we are allowed to rent reconfigurable but expensive resources to use across scenarios. Although computing the objective in our model might seem to require enumerating exponentially-many possibilities, we show it is well estimated by a surrogate objective which is representable by a polynomial-size LP. In this surrogate objective we pay for each scenario only to the extent that it exceeds a certain threshold. Using this objective we design algorithms that approximately-optimally balance inflexible and reconfigurable resources for several NP-hard covering problems. For example, we study variants of minimum spanning and Steiner trees, minimum cuts, and facility location. Up to constants, our approximation guarantees match those of previously-studied algorithms for demand-robust and stochastic two-stage models. Lastly, we demonstrate that our problem is sufficiently general to smoothly interpolate between previous demand-robust and stochastic two-stage problems.

BibTeX - Entry

@InProceedings{hershkowitz_et_al:LIPIcs:2019:11219,
  author =	{David Ellis Hershkowitz and R. Ravi and Sahil Singla},
  title =	{{Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11219},
  URN =		{urn:nbn:de:0030-drops-112196},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.4},
  annote =	{Keywords: Approximation Algorithms, Optimization Under Uncertainty, Two-Stage Optimization, Expected Max}
}

Keywords: Approximation Algorithms, Optimization Under Uncertainty, Two-Stage Optimization, Expected Max
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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