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.2016.8
URN: urn:nbn:de:0030-drops-66319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6631/
Go to the corresponding LIPIcs Volume Portal

Feige, Uriel ; Feldman, Michal ; Talgam-Cohen, Inbal

Oblivious Rounding and the Integrality Gap

pdf-format:
LIPIcs-APPROX-RANDOM-2016-8.pdf (0.5 MB)

Abstract

The following paradigm is often used for handling NP-hard combinatorial optimization problems. One first formulates the problem as an integer program, then one relaxes it to a linear program (LP, or more generally, a convex program), then one solves the LP relaxation in polynomial time, and finally one rounds the optimal LP solution, obtaining a feasible solution to the original problem. Many of the commonly used rounding schemes (such as randomized rounding, threshold rounding and others) are "oblivious" in the sense that the rounding is performed based on the LP solution alone, disregarding the objective function. The goal of our work is to better understand in which cases oblivious rounding suffices in order to obtain approximation ratios that match the integrality gap of the underlying LP. Our study is information theoretic - the rounding is restricted to be oblivious but not restricted to run in polynomial time. In this information theoretic setting we characterize the approximation ratio achievable by oblivious rounding. It turns out to equal the integrality gap of the underlying LP on a problem that is the closure of the original combinatorial optimization problem. We apply our findings to the study of the approximation ratios obtainable by oblivious rounding for the maximum welfare problem, showing that when valuation functions are submodular oblivious rounding can match the integrality gap of the configuration LP (though we do not know what this integrality gap is), but when valuation functions are gross substitutes oblivious rounding cannot match the integrality gap (which is 1).

BibTeX - Entry

@InProceedings{feige_et_al:LIPIcs:2016:6631,
  author =	{Uriel Feige and Michal Feldman and Inbal Talgam-Cohen},
  title =	{{Oblivious Rounding and the Integrality Gap}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6631},
  URN =		{urn:nbn:de:0030-drops-66319},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.8},
  annote =	{Keywords: Welfare-maximization}
}

Keywords: Welfare-maximization
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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