论文标题
分离最大2和最大切割和最大切割
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
论文作者
论文摘要
假设有独特的游戏猜想（UGC），最大切割问题中可以在多项式时间获得的最佳近似值为$α_ {\ text {cut}} \ simeq 0.87856 $，由著名的基于SDP的Gogoys and Williamson的基于著名的SDP近似Algorithm获得。当前最佳最大DI切割的最佳近似算法，即有向图中的最大切割问题，达到了约0.87401美元的比率，留下了一个问题，却打开了一个问题，是否可以将最大di-cut近似以及最大切口。 We obtain a slightly improved algorithm for MAX DI-CUT and a new UGC-hardness result for it, showing that $0.87446\le α_{\text{DI-CUT}}\le 0.87461$, where $α_{\text{DI-CUT}}$ is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT在UGC下。新的上限将Max Di cut与Max Cut分开，从而解决了Feige和Goemans提出的问题。 最大di切割的自然概括是最大2，是每个约束的$ z_1 \ land z_2 $的问题，其中$ z_1 $和$ z_2 $是字面的，即变量或它们的否定（在最大di cout中，每种约束都属于$ \ bar $ \ bar \ bar {x} _1 _1 $ x________________ $ x_1 $ x_1 $ x_1 $ x_1 $ x_1 $ x_1 $ x_1 $ x_1 $ x $ x_1分开的最大2和从最大切割的分离，表明$α_ {\ text {2 and}} <0.87435 $，并猜想max 2和max di-cut具有相同的近似值。我们在最大界限上的新下限驳斥了这一猜想，完成了三个问题的分离最大2，最大di-cut和max cut。我们还获得了最大2的新下限，并表明$ 0.87414 \leα_ {\ text {2 and}}} \ le 0.87435 $。 我们在最大二线上的上限是通过简单的，分析的证明来实现的。最大切割和最大2和（新的近似算法）的下限使用圆形功能的实验发现的分布，然后通过计算机辅助的证明进行验证。
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is $α_{\text{CUT}}\simeq 0.87856$, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about $0.87401$, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UGC-hardness result for it, showing that $0.87446\le α_{\text{DI-CUT}}\le 0.87461$, where $α_{\text{DI-CUT}}$ is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form $z_1\land z_2$, where $z_1$ and $z_2$ are literals, i.e., variables or their negations (In MAX DI-CUT each constraint is of the form $\bar{x}_1\land x_2$, where $x_1$ and $x_2$ are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that $α_{\text{2AND}} < 0.87435$ and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND, showing that $0.87414\le α_{\text{2AND}}\le 0.87435$. Our upper bound on MAX DI-CUT is achieved via a simple, analytical proof. The lower bounds on MAX DI-CUT and MAX 2-AND (the new approximation algorithms) use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs.
