Publikation: A Bundle Approach for SDPs with Exact S...
Stammdaten
Titel: | A Bundle Approach for SDPs with Exact Subgraph Constraints |
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 two independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach. |
Schlagworte: | Semidefinite programming, Relaxation hierarchy, Max-Cut, Stable set, Coloring |
Publikationstyp: | Beitrag in Proceedings (Autorenschaft) |
Erscheinungsdatum: | 13.04.2019 (Print) |
Erschienen in: |
IPCO 2019: Integer Programming and Combinatorial Optimization
IPCO 2019: Integer Programming and Combinatorial Optimization
(
Springer;
)
zur Publikation |
Titel der Serie: | Lecture Notes in Computer Science |
Bandnummer: | 11480 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 205 - 218 |
Bild der Titelseite: |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1007/978-3-030-17953-3_16 |
Homepage: | - |
Open Access |
|
Erscheinungsdatum: | 13.04.2019 |
ISBN: |
|
ISSN: | - |
Homepage: | https://link.springer.com/chapter/10.1007/978-3-030-17953-3_16 |
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 |
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: |
|