期刊
THEORETICAL COMPUTER SCIENCE
卷 348, 期 2-3, 页码 357-365出版社
ELSEVIER
DOI: 10.1016/j.tcs.2005.09.023
关键词
exact algorithms; constraint satisfaction; MAX-2-SAT; MAX-CUT
We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm. More precisely, the runtime bound is a constant factor improvement in the base of the exponent: the algorithm can count the number of optima in MAX-2-SAT and MAX-CUT instances in O(m(3)2(omega n/3)) time, where omega < 2.376 is the matrix product exponent over a ring. When the constraints have arbitrary weights, there is a (1 + epsilon)-approximation with roughly the same runtime, modulo polynomial factors. Our construction shows that improvement in the runtime exponent of either k-clique solution (even when k = 3) or matrix multiplication over G F(2) would improve the runtime exponent for solving 2-CSP optimization. Our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter of n points in l(1), then there is an (2 - epsilon)(n) algorithm for MAX-LIN. These results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems. (c) 2005 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据