Publikation: An SDP-based approach for computing the...
Stammdaten
Titel: | An SDP-based approach for computing the stability number of a graph |
Untertitel: | |
Kurzfassung: | Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this problem has several applications in real life, there is need to find efficient algorithms to solve this problem. Recently, Gaar and Rendl enhanced semidefinite programming approaches to tighten the upper bound given by the Lovász theta function. This is done by carefully selecting some so-called exact subgraph constraints (ESC) and adding them to the semidefinite program of computing the Lovász theta function. First, we provide two new relaxations that allow to compute the bounds faster without substantial loss of the quality of the bounds. One of these two relaxations is based on including violated facets of the polytope representing the ESCs, the other one adds separating hyperplanes for that polytope. Furthermore, we implement a branch and bound (B&B) algorithm using these tightened relaxations in our bounding routine. We compare the efficiency of our B&B algorithm using the different upper bounds. It turns out that already the bounds of Gaar and Rendl drastically reduce the number of nodes to be explored in the B&B tree as compared to the Lovász theta bound. However, this comes with a high computational cost. Our new relaxations improve the run time of the overall B&B algorithm, while keeping the number of nodes in the B&B tree small. |
Schlagworte: | Stable Set, Semidefinite programming, Lovasz theta function, Branch and bound, Combinatorial optimization |
Publikationstyp: | Beitrag in Zeitschrift (Autorenschaft) |
Erscheinungsdatum: | 12.03.2022 (Online) |
Erschienen in: |
Mathematics of Operations Research
Mathematics of Operations Research
(
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 95 |
Heftnummer: | 1 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 141 - 161 |
Bild der Titelseite: |
|
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 02.2022 |
ISBN: | - |
ISSN: | 1432-2994 |
Homepage: | https://link.springer.com/article/10.1007/s00186-022-00773-1 |
Erscheinungsdatum: | 12.03.2022 |
ISBN (e-book): | - |
eISSN: | 1432-5217 |
DOI: | http://dx.doi.org/10.1007/s00186-022-00773-1 |
Homepage: | https://link.springer.com/article/10.1007/s00186-022-00773-1 |
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 |
|
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Johannes Kepler Universität Linz
|
AT - 4040 Linz |
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 |