Contraction-based Separation and Lifting for Solving the Max-Cut Problem
Produktnummer:
18587716e48d4c476c8fd611cd5b0534d8
| Autor: | Bonato, Thorsten |
|---|---|
| Themengebiete: | Mathematik artificial extension branch-and-cut combinatorial optimization cut polytope graph contraction lifting max-cut problem odd-cycle inequality polyhedral combinatorics projection separation target cuts unconstrained quadratic 0-1 optimization |
| Veröffentlichungsdatum: | 18.11.2011 |
| EAN: | 9783941274860 |
| Auflage: | 1 |
| Sprache: | Englisch |
| Seitenzahl: | 197 |
| Produktart: | Kartoniert / Broschiert |
| Verlag: | Sievers & Partner |
Produktinformationen "Contraction-based Separation and Lifting for Solving the Max-Cut Problem"
The max-cut problem is an NP-hard combinatorial optimization problem defined on undirected weighted graphs. It consists in finding a subset of the graph's nodes such that the aggregate weight of the edges between the subset and its complement is maximized. This book deals with a new separation approach to be used within a branch-and-cut algorithm for solving max-cut problems to optimality. The method is based on graph contraction and allows the fast separation of so-called odd-cycle inequalities. In addition, we describe techniques to add possibly missing edges to an already contracted graph. This allows solving max-cut problems on sparse graphs by means of methods that were originally intended for complete graphs and could not have been applied otherwise. We investigate the theoretical aspects of this combined approach and also explain its realization within a branch-and-cut framework. Finally, we evaluate the performance of our separation procedure on a variety of test instances.
Sie möchten lieber vor Ort einkaufen?
Sie haben Fragen zu diesem oder anderen Produkten oder möchten einfach gerne analog im Laden stöbern? Wir sind gerne für Sie da und beraten Sie auch telefonisch.
Juristische Fachbuchhandlung
Georg Blendl
Parcellistraße 5 (Maxburg)
8033 München
Montag - Freitag: 8:15 -18 Uhr
Samstags geschlossen