Abstract
The following paradigm is often used for handling NPhard 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 TalgamCohen},
title = {{Oblivious Rounding and the Integrality Gap}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {8:18:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6631},
URN = {urn:nbn:de:0030drops66319},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.8},
annote = {Keywords: Welfaremaximization}
}
Keywords: 

Welfaremaximization 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 