Publikation: A computational study of exact subgraph...
Stammdaten
Titel: | A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring |
Untertitel: | |
Kurzfassung: | The “exact subgraph” approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach. |
Schlagworte: | Semidefinite Programming, Max-Cut, stable set, coloring |
Publikationstyp: | Beitrag in Zeitschrift (Autorenschaft) |
Erscheinungsdatum: | 25.05.2020 (Online) |
Erschienen in: |
Mathematical Programming
Mathematical Programming
(
Springer Verlag GmbH;
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 183 |
Heftnummer: | 1-2 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 283 - 308 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 25.05.2020 |
ISBN (e-book): | - |
eISSN: | 1436-4646 |
DOI: | http://dx.doi.org/10.1007/s10107-020-01512-2 |
Homepage: | https://link.springer.com/article/10.1007/s10107-020-01512-2 |
Open Access |
|
AutorInnen
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Zitationsindex |
Informationen zum Zitationsindex: Master Journal List
|
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: |
|
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: | Keine verknüpften Veranstaltung vorhanden |
Vorträge: | Keine verknüpften Vorträge vorhanden |