Universität zu Köln

Anjos, Miguel F., Liers, Frauke, Pardella, Gregor and Schmutzer, Andreas (2013). Engineering Branch-and-Cut Algorithms for the Equicut Problem. In: Discrete Geometry and Optimization, Berlin: Springer.

Preview

PDF main.pdf Download (313kB) | Preview

Abstract

A minimum equicut of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such hat the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefnite relaxations for the equicut problem, and and that linear bounds are competitive with the corresponding semidefnite ones but can be computed much faster. Motivated by an application of equicut in theoretical physics, we revisit an approach by Brunetta et al. and present an enhanced branch-and-cut algorithm. Our computational results suggest that the proposed branch-andcut algorithm has a better performance than the algorithm of Brunetta et al.. Further, it is able to solve to optimality in reasonable time several instances with more than 200 nodes from the physics application.

Item Type:	Book Section
Creators:	Creators Email ORCID ORCID Put Code Anjos, Miguel F. UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Pardella, Gregor UNSPECIFIED UNSPECIFIED UNSPECIFIED Schmutzer, Andreas UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550280
Title of Book:	Discrete Geometry and Optimization
Journal or Publication Title:	Proceedings of the Thematic Program on Discrete Geometry and Applications
Series Name:	Fields Institute Communications
Volume:	69
Date:	2013
Publisher:	Springer
Place of Publication:	Berlin
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55028