Stammdaten

Titel: Efficient Implementation of SDP Relaxations for the Stable Set Problem
Untertitel:
Kurzfassung:

The stable set problem is among the most prominent problems of combinatorial optimization. Given a graph, it asks for a maximum stable set, that is a set of vertices such that no two vertices are adjacent of largest possible cardinality. The cardinality of such a maximum stable set is called the stability number.

 The stable set problem is NP-complete, hence there is no polynomial time algorithm to solve the stable set problem exactly unless P=NP. In order to solve the stable set problem exactly with a branch-and-bound algorithm tight upper bounds on the stability number are required. One possible upper bound is given by the Lovász theta function, which can be computed as semidefinite program (SDP). In order to improve this upper bound one can add so-called exact subgraph constraints (ESCs) for some wisely chosen subgraphs into this SDP. For a certain subgraph, the ESC ensures that the submatrix of the calculation of the Lovász theta function corresponding to the subgraph is contained in the convex hull of all stable set matrices of the subgraph.

 The aim of this thesis it to computationally exploit ESCs in order to get improved upper bounds on the stability number. Towards that end three different possibilities to include the ESCs into the SDP are presented. Furthermore a specialized solution algorithm based on the bundle method in order to solve the resulting SDP fast is developed. Moreover methods to determine the subgraphs for which the ESC should be included are discussed.

Schlagworte:
Publikationstyp: Hochschulschrift (nicht publiziert) (Autorenschaft)
Art der Veröffentlichung Printversion
Erscheinungsdatum: 14.05.2018
Titel der Serie: -
Bandnummer: -
Erstveröffentlichung: Ja
Gesamtseitenanzahl: 172 S.

Identifikatoren

ISBN: -
ISSN: -
DOI: -
AC-Nummer: -
Homepage:
Open Access
  • Kein Open-Access

AutorInnen

Zuordnung

Organisation Adresse
Fakultät für Technische Wissenschaften
 
Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   mirjam.jonk@aau.at
https://www.aau.at/mathematik
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Verlag

Organisation Adresse
Hochschulschrift
Österreich
AT  

Kategorisierung

Sachgebiete
  • 101011 - Graphentheorie
  • 101015 - Operations Research
  • 101016 - Optimierung
Forschungscluster Kein Forschungscluster ausgewählt
Peer Reviewed
  • Ja
Publikationsfokus
  • Science to Science (Qualitätsindikator: n.a.)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Kooperationen

Keine Partnerorganisation ausgewählt

Beiträge der Publikation

Keine verknüpften Publikationen vorhanden