Towards a Characterization of Constant-Factor Approximable Min CSPs
Towards a Characterization of Constant-Factor Approximable Min CSPs
复制标题
常数因子近似最小 CSP 的表征
DOI：
10.1137/1.9781611973730.58
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Dalmau V
中科院分区：
文献类型：
--
作者：
Dalmau V
研究了任意有限区域上固定有限约束语言Γ的最小约束满足问题（MinCSP）的可逼近性.这样的问题的目标是最小化CSP（r）的给定实例中未满足的约束的数量。Eneet等人最近的一个结果表明，在Γ包含等式关系的温和技术条件下，基本LP松弛对于Min CSP（Γ）的常数因子逼近是最优的，除非唯一博弈猜想失败。利用CSP的代数方法，我们引入了一个新的自然代数条件，约束语言的对称多态性上的稳定概率分布，并证明了对于Min CSP（Γ）的基本LP松弛的完整性间隙的有限性，每个元的多态性上的这种分布的存在是必要的和充分的.我们还展示了对称多态性上的稳定分布如何在原则上被用来对基本LP松弛的解进行舍入，以及如何在覆盖所有先前已知情况的几个例子中，这导致了Min CSP（Γ）的有效常数因子近似算法。最后，我们证明了另一个条件的情况下，这是由稳定的分布所隐含的，导致NP-硬度的常数因子近似。
We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Eneet al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation.
登录
查看更多内容
论独特游戏猜想（特邀调查）
DOI：
--
发表时间：
2005
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
Subhash Khot
通讯作者：
Subhash Khot
用于多向切割、0 延伸和公制标签的 Sdp 间隙和 ugc 硬度
DOI：
--
发表时间：
2008
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. Manokaran;Joseph Naor;Prasad Raghavendra;Roy Schwartz
通讯作者：
Roy Schwartz
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Sanjeev Arora;R. Manokaran
通讯作者：
R. Manokaran
近乎一致的约束限制了路径宽度对偶性
DOI：
--
发表时间：
2012
期刊：
2012 27th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
L. Barto;M. Kozik;R. Willard
通讯作者：
R. Willard
具有平衡/硬约束的近似 CSP 的复杂性
影响因子：
0.5
作者：
V. Guruswami;Euiwoong Lee
通讯作者：
Euiwoong Lee