Oblivious Rounding and the Integrality Gap
Oblivious Rounding and the Integrality Gap
复制标题
不经意的舍入和完整性差距
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi
中科院分区：
文献类型：
--
作者：
Sepehr Assadi
下面的范例通常用于处理NP-Hard组合优化问题。首先将问题表示为整数规划，然后将其松弛为线性规划(LP，或者更一般地说，凸规划)，然后在多项式时间内求解LP松弛，最后对最优线性规划解进行循环，得到原问题的可行解。许多常用的舍入方案(例如随机舍入、阈值舍入等)在仅基于Lp解而忽略目标函数的意义上执行舍入。我们工作的目标是更好地理解在哪些情况下不经意舍入就足够了，以便获得与潜在LP的完整性间隙相匹配的逼近比。我们的研究是信息论的--舍入被限制为忽略，但不限于在多项式时间内运行。在这种信息论的背景下，我们刻画了不经意舍入所能达到的逼近比。结果表明，在原组合优化问题的闭包问题上，它等于底层线性规划的完整性间隙。将我们的结果应用于对最大福利问题不经意舍入所能获得的逼近比的研究，表明当赋值函数是子模时，不经意舍入可以匹配配置Lp的完整性间隙(虽然我们不知道这个完整性缺口是什么)，但当估值函数是粗代换时，不经意舍入不能匹配完整性缺口(1)。
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).