Bonato, Thorsten, Jünger, Michael, Reinelt, Gerhard and Rinaldi, Giovanni ORCID: 0000-0003-0148-2470 (2013). Lifting and Separation Procedures for the Cut Polytope. Mathematical Programming A. Springer.

[img]
Preview
PDF
mc_V9.pdf - Submitted Version

Download (350kB) | Preview

Abstract

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, little research has been conducted for the cut polytope on arbitrary graphs. In this study we describe new separation and lifting procedures for the cut polytope on such graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Bonato, ThorstenUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Reinelt, GerhardUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Rinaldi, GiovanniUNSPECIFIEDorcid.org/0000-0003-0148-2470UNSPECIFIED
URN: urn:nbn:de:hbz:38-550246
Journal or Publication Title: Mathematical Programming A
Date: 2013
Publisher: Springer
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/55024

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item