Improving the linear relaxation of maximum k-cut with semidefinite-based constraints

We consider the maximum k-cut problem that involves partitioning the vertex set of a graph into k subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	VilmarJefté Rodrigues de Sousa, MiguelF. Anjos, Sébastien Le Digabel
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	65K05 90C22 90C35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e83f83c8eb1e402f83fc6eed4310cd7b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e83f83c8eb1e402f83fc6eed4310cd7b
record_format	dspace
spelling	oai:doaj.org-article:e83f83c8eb1e402f83fc6eed4310cd7b2021-12-02T05:01:11ZImproving the linear relaxation of maximum k-cut with semidefinite-based constraints2192-440610.1007/s13675-019-00110-yhttps://doaj.org/article/e83f83c8eb1e402f83fc6eed4310cd7b2019-06-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001131https://doaj.org/toc/2192-4406We consider the maximum k-cut problem that involves partitioning the vertex set of a graph into k subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We use a cutting-plane algorithm that relies on the early termination of an interior point method, and we study the performance of SDP and linear programming (LP) relaxations for various values of k and instance types. The LP relaxation is strengthened using combinatorial facet-defining inequalities and SDP-based constraints. Our computational results suggest that the LP approach, especially with the addition of SDP-based constraints, outperforms the SDP relaxations for graphs with positive-weight edges and k≥7.VilmarJefté Rodrigues de SousaMiguelF. AnjosSébastien Le DigabelElsevierarticle65K0590C2290C35Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 2, Pp 123-151 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	65K05 90C22 90C35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	65K05 90C22 90C35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 VilmarJefté Rodrigues de Sousa MiguelF. Anjos Sébastien Le Digabel Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
description	We consider the maximum k-cut problem that involves partitioning the vertex set of a graph into k subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We use a cutting-plane algorithm that relies on the early termination of an interior point method, and we study the performance of SDP and linear programming (LP) relaxations for various values of k and instance types. The LP relaxation is strengthened using combinatorial facet-defining inequalities and SDP-based constraints. Our computational results suggest that the LP approach, especially with the addition of SDP-based constraints, outperforms the SDP relaxations for graphs with positive-weight edges and k≥7.
format	article
author	VilmarJefté Rodrigues de Sousa MiguelF. Anjos Sébastien Le Digabel
author_facet	VilmarJefté Rodrigues de Sousa MiguelF. Anjos Sébastien Le Digabel
author_sort	VilmarJefté Rodrigues de Sousa
title	Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
title_short	Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
title_full	Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
title_fullStr	Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
title_full_unstemmed	Improving the linear relaxation of maximum k-cut with semidefinite-based constraints
title_sort	improving the linear relaxation of maximum k-cut with semidefinite-based constraints
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/e83f83c8eb1e402f83fc6eed4310cd7b
work_keys_str_mv	AT vilmarjefterodriguesdesousa improvingthelinearrelaxationofmaximumkcutwithsemidefinitebasedconstraints AT miguelfanjos improvingthelinearrelaxationofmaximumkcutwithsemidefinitebasedconstraints AT sebastienledigabel improvingthelinearrelaxationofmaximumkcutwithsemidefinitebasedconstraints
_version_	1718400862890491904

Improving the linear relaxation of maximum k-cut with semidefinite-based constraints

Ejemplares similares