Approximability and mathematical relaxations
Approximability and mathematical relaxations
复制标题
近似性和数学松弛
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. Manokaran
中科院分区：
文献类型：
--
作者：
Sanjeev Arora;R. Manokaran
本文用数学松弛法确定了经典组合优化问题的近似性。论文结果的一般风格是：一个问题P很难近似于一个比从R松弛得到的更好的因子，除非唯一游戏猜想是假的。
The thesis ascertains the approximability of classic combinatorial optimization problems using mathematical relaxations. The general flavor of results in the thesis is: a problem P is hard to approximate to a factor better than one obtained from the R relaxation, unless the Unique Games Conjecture is false.
Almost optimal inapproximability is shown for a wide set of problems including Metric Labeling, Max. Acyclic Subgraph, various packing and covering problems. The key new idea in this thesis is in coverting hard instances of relaxations (a.k.a integrality gap instances) into a proof of inapproximability (assuming the UGC). In most cases, the hard instances were discovered prior to this work; our results imply that these hard instances are possibly strong bottlenecks in designing approximation algorithms of better quality for these problems.
For ordering problems such as Max Acyclic Subgraph and Feedback Arc Set such hard instances were previously unknown. For these problems, we construct such hard instance by using the reduction designed to prove the inapproximability. The hard instances show that all ordering problems are hard to approximate to a factor larger than the expected fraction satisfied by a random ordering: i.e., all ordering CSPs are approximation resistant.
Techniques involve using mathematical relaxations to obtain local distributions, converting them into low degree functions defined over the boolean cube and using the invariance principle to analyse such function.
I believe the thesis will be a good reference, both for the results proven therein, and for the framework designed in ascertaining approximability from mathematical relaxations.