论文标题
改进的组合近似算法以稀疏图切割
Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs
论文作者
论文摘要
最大切割的问题是一个基本的NP - 硬性问题，如今，它引起了量子计算领域的关注。关于最大切割问题的近似算法，基于半芬矿编程的算法比组合算法的近似值率要好得多。因此，填补空白是一个有趣的话题，因为组合算法也具有一些优点。在稀疏图中，有一个线性时间组合算法，其近似值比$ \ frac {1} {2} {2}+\ frac {n-1} {4M} $ [ngoc and tuza，comb。概率。计算。 1993]，被称为Edwards-erdősBound。在亚皮图中，Bazgan和Tuza的组合算法[离散数学。 2008]具有最佳的近似值$ \ frac {5} {6} $，以$ o（n^2）$时间运行。基于Bazgan和Tuza的方法，我们引入了一个新的顶点分解图，我们将其称为Tree-tightite分解。通过分解，我们提出了一个线性时$（\ frac {1} {2}+\ frac {n-1} {2m}）$ - 最大切割问题的近似算法。作为派生型，我们还提供了一个线性时间$ \ frac {5} {6} $ - 亚立方图中的近似算法，该算法在他们的论文中解决了一个开放的问题。
The Max-Cut problem is a fundamental NP-hard problem, which is attracting attention in the field of quantum computation these days. Regarding the approximation algorithm of the Max-Cut problem, algorithms based on semidefinite programming have achieved much better approximation ratios than combinatorial algorithms. Therefore, filling the gap is an interesting topic as combinatorial algorithms also have some merits. In sparse graphs, there is a linear-time combinatorial algorithm with the approximation ratio $\frac{1}{2}+\frac{n-1}{4m}$ [Ngoc and Tuza, Comb. Probab. Comput. 1993], which is known as the Edwards-Erdős bound. In subcubic graphs, the combinatorial algorithm by Bazgan and Tuza [Discrete Math. 2008] has the best approximation ratio $\frac{5}{6}$ that runs in $O(n^2)$ time. Based on the approach by Bazgan and Tuza, we introduce a new vertex decomposition of graphs, which we call tree-bipartite decomposition. With the decomposition, we present a linear-time $(\frac{1}{2}+\frac{n-1}{2m})$-approximation algorithm for the Max-Cut problem. As a derivative, we also present a linear-time $\frac{5}{6}$-approximation algorithm in subcubic graphs, which solves an open problem in their paper.
