Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
复制标题
粘性布朗舍入及其在约束满足问题中的应用
DOI：
10.1137/1.9781611975994.52
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Singh, M.
中科院分区：
文献类型：
--
作者：
Abbasi-Zadeh, S;Bansal, N;Guruganesh, G.;Nikolov, A;Schwartz, R;Singh, M.
半定规划是设计和分析组合优化问题近似算法的有力工具。特别是Goemans和Williamson的随机超平面舍入方法已经被广泛研究了二十多年，产生了对原始技术的各种扩展和美观的算法，用于广泛的应用。尽管这种方法对某些问题（例如Max-Cut）产生了严格的近似保证，但对于许多其他问题（例如Max-SATandMax-DiCut），严格的近似比仍然未知。造成这种情况的一个主要原因是，已知的舍入半确定松弛的技术很少。在本文中，我们提出了一种新的基于布朗运动的半确定规划舍入的一般简便方法。我们的方法受到算法差异理论的启发。我们开发并展示了分析我们新的舍入算法的工具，利用布朗运动理论、复杂分析和偏微分方程的数学机制。关注约束满足问题，我们将我们的方法应用于几个经典问题，包括max - cut，Max-2SAT和max - dicut，并推导出与已知结果相竞争的新算法。为了说明我们方法的通用性和一般适用性，我们给出了具有侧约束的max - cut问题的新近似算法，该算法关键地利用了粘布朗运动的测量集中结果，粘布朗运动是超平面舍入及其推广中缺少的一个特征。
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g.,Max-Cut, for many others, e.g.,Max-SATandMax-DiCut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known.In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, includingMax-Cut,Max-2SAT, andMax-DiCut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for theMax-Cutproblem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.
登录
查看更多内容
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
平衡最大 2-sat 可能不是最难的
DOI：
10.1145/1250790.1250818
发表时间：
2007
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Per Austrin
通讯作者：
Per Austrin
全局基数约束使得近似某些 Max-2-CSP 变得更加困难
DOI：
10.4230/lipics.approx-random.2019.24
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Per Austrin;A. Stankovic
通讯作者：
A. Stankovic
如何舍入任何 CSP
DOI：
10.1109/focs.2009.74
发表时间：
2009
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
P. Raghavendra;David Steurer
通讯作者：
David Steurer
MAX SAT 的 Geomans 和 Williamson LP 松弛的改进分析
DOI：
--
发表时间：
2003
期刊：
Proceedings of the 14th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science 2751, Springer 14
影响因子：
--
作者：
Takao Asano
通讯作者：
Takao Asano