IMPROVED ANALYSIS OF A MAX-CUT ALGORITHM BASED ON SPECTRAL PARTITIONING

被引：9

作者：

Soto, Jose A. ^{[1
,2
]}

机构：

[1] Univ Chile, Dept Ingn Matemat, Santiago, Chile

[2] Univ Chile, UMI CNRS 2807, Ctr Modelamiento Matemat, Santiago, Chile

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2015年 / 29卷 / 01期

关键词：

max-cut; spectral graph theory; spectral partitioning; approximation algorithms;

D O I：

10.1137/14099098X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem.

引用

页码：259 / 268

页数：10