2019/04/15 by André Linhares, Linhares, Andre, Chaitanya Swamy +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.1.6 #G.2 #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1904.07381
openalex publication_date 2019/04/15 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Two-stage stochastic optimization is a framework for modeling uncertainty,\nwhere we have a probability distribution over possible realizations of the\ndata, called scenarios, and decisions are taken in two stages: we make\nfirst-stage decisions knowing only the underlying distribution and before a\nscenario is realized, and may take additional second-stage recourse actions\nafter a scenario is realized. The goal is typically to minimize the total\nexpected cost. A criticism of this model is that the underlying probability\ndistribution is itself often imprecise! To address this, a versatile approach\nthat has been proposed is the em distributionally robust 2-stage model:\ngiven a collection of probability distributions, our goal now is to minimize\nthe maximum expected total cost with respect to a distribution in this\ncollection.\n We provide a framework for designing approximation algorithms in such\nsettings when the collection is a ball around a central distribution and the\ncentral distribution is accessed em only via a sampling black box.\n We first show that one can utilize the em sample average approximation\n(SAA) method to reduce the problem to the case where the central distribution\nhas em polynomial-size support. We then show how to approximately solve a\nfractional relaxation of the SAA (i.e., polynomial-scenario\ncentral-distribution) problem. By complementing this via LP-rounding algorithms\nthat provide em local (i.e., per-scenario) approximation guarantees, we\nobtain the em first approximation algorithms for the distributionally robust\nversions of a variety of discrete-optimization problems including set cover,\nvertex cover, edge cover, facility location, and Steiner tree, with guarantees\nthat are, except for set cover, within O(1)-factors of the guarantees known\nfor the deterministic version of the problem.\n