New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
复制标题
MAX-2-SAT 和 MAX-2-CSP 的新上限
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Alexander Golovnev
中科院分区：
文献类型：
--
作者：
Alexander Golovnev
MAX-2-SAT 和 MAX-2-CSP 是重要的 NP 难优化问题，概括了许多图问题。尽管付出了很多努力，但唯一已知的算法（由 Williams 提出）使用指数空间以不到 2n 步的速度求解它们。 Scott 和 Sorkin 针对这些问题给出了一个具有 2n(1 - 2/{d+1}) 时间和多项式空间的算法，其中 d 是平均变量度。对于 MAX-2-SAT，我们将此界限改进为 O*(2n(1- {10/3}/{d+1}))；对于 MAX-2-CSP，我们将其改进为 O*(2n(1- 3/{d+1}))。我们还证明了 d 的下界有更强的上限。例如，对于 d≥10，界限分别改进为 O*(2n(1- {3.469}/{d+1})) 和 O*(2n(1- {3.221}/{d+1}))。作为副产品，我们得到了 MAX-2-CSP 的 O*(2m/5.263) 上限的简单证明，其中 m 是约束数量。这与最著名的上限相匹配。感谢加斯帕斯和索金。
MAX-2-SAT and MAX-2-CSP are important NP-hard optimization problems generalizing many graph problems. Despite many efforts, the only known algorithm (due to Williams) solving them in less than 2n steps uses exponential space. Scott and Sorkin give an algorithm with 2n(1 - 2/{d+1}) time and polynomial space for these problems, where d is the average variable degree. We improve this bound to O*(2n(1- {10/3}/{d+1})) for MAX-2-SAT and O*(2n(1- 3/{d+1})) for MAX-2-CSP. We also prove stronger upper bounds for d bounded from below. E.g., for d≥10 the bounds improve to O*(2n(1- {3.469}/{d+1})) and O*(2n(1- {3.221}/{d+1})), respectively. As a byproduct we get a simple proof of an O*(2m/5.263) upper bound for MAX-2-CSP, where m is the number of constraints. This matches the best known upper bound w.r.t. m due to Gaspers and Sorkin.
SOFSEM 2007：计算机科学的理论与实践
DOI：
10.1007/978-3-540-69507-3_15
发表时间：
2007
期刊：
--
影响因子：
--
作者：
Broersma H
通讯作者：
Broersma H