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.
|
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, Proceedings Item or annotation in a legal commentary | ||||||||||||||||||||
| Creators: |
|
||||||||||||||||||||
| 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 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |