Improved analysis of a max-cut algorithm based on spectral partitioning

Author	dc.contributor.author	Soto San Martín, José
Admission date	dc.date.accessioned	2015-07-09T18:10:08Z
Available date	dc.date.available	2015-07-09T18:10:08Z
Publication date	dc.date.issued	2015
Cita de ítem	dc.identifier.citation	SIAM J. DISCRETE MATH. 2015 Vol. 29, No. 1, pp. 259–268	en_US
Identifier	dc.identifier.other	DOI: 10.1137/14099098X
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/131885
General note	dc.description	Artículo de publicación ISI	en_US
Abstract	dc.description.abstract	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.	en_US
Lenguage	dc.language.iso	en_US	en_US
Publisher	dc.publisher	SIAM	en_US
Type of license	dc.rights	Atribución-NoComercial-SinDerivadas 3.0 Chile	*
Link to License	dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/cl/	*
Keywords	dc.subject	max-cut	en_US
Keywords	dc.subject	spectral graph theory	en_US
Keywords	dc.subject	spectral partitioning	en_US
Keywords	dc.subject	approximation algorithms	en_US
Título	dc.title	Improved analysis of a max-cut algorithm based on spectral partitioning	en_US
Document type	dc.type	Artículo de revista

Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile