Vortrag: A class of new cutting planes for SDP relaxations of stable set and c...
Stammdaten
Titel: | A class of new cutting planes for SDP relaxations of stable set and colouring problems |
Beschreibung: | Stable set and colouring problems are fundamental combinatorial optimization problems. A standard method in combinatorial optimization is to write a problem as a linear problem with integer variables, and then to consider its relaxation in order to get bounds on the optimal solution. This research focuses on bounds which are obtained by semidefinite relaxations using semidefinite programming. A famous semidefinite relaxation for both stable set and colouring problems is the Lovász theta function. We consider tightening of the Lovász theta function which can be achieved by adding valid inequalities into the formulation. We combine the ideas of some of the existing inequalities and derive new cutting planes for both problems. Finally, we investigate the bounds obtained by adding the proposed inequalities. We compare our bounds with existing relaxations and present computational results. |
Schlagworte: |
Typ: | Angemeldeter Vortrag |
Homepage: | http://www.airoconference.it/ods2023/ |
Veranstaltung: | ODS 2023, International Conference on Optimization and Decision Science (Ischia) |
Datum: | 06.09.2023 |
Vortragsstatus: | stattgefunden (Präsenz) |
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 |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Arbeitsgruppen |
|
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 |