

























We present a new simple method for rounding a semidefinite programming relaxation of a constraint satisfaction problem. We apply it to the problem of approximate angular synchronization. Specifically, we are given directed distances on a circle (i.e., directed angles) between pairs of elements and our goal is to assign the elements to positions on a circle so as to preserve these distances as much as possible. The feasibility of our rounding scheme is based on properties of the well-known stochastic process called Brownian motion. Based on computational and other evidence, we conjecture that this rounding scheme yields an approximation guarantee that is very close to the best-possible guarantee (assuming the Unique-Games Conjecture).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。