Vortrag: The exact subgraph relaxation meets the Lasserre hierarchy
Stammdaten
Titel: | The exact subgraph relaxation meets the Lasserre hierarchy |
Beschreibung: | The exact subgraph relaxation in combination with semidefinite optimization has recently turned out to be a very powerful tool for Max-Cut, Stable-Set and Colouring. It works with a basic SDP relaxation, typically in matrices of order $n$, and incrementally adds 'exact subgraph' constraints to the relaxation. In contrast, the Lasserre hierarchy moves to matrix relaxations, which are unpractical even in the first nontrivial step (typically matrices of order ${n \choose 2}$. In this talk we explore relations between the two seemingly quite different approaches. We show in particular how a slightly weakened version of the Lasserre relaxations can be dealt with in the space of matrices of order $n$. Preliminary computational results are given and look encouraging. |
Schlagworte: |
Typ: | Angemeldeter Vortrag |
Homepage: | http://www.iasi.cnr.it/aussois/web/home/program/year/2020 |
Veranstaltung: | 24th COMBINATORIAL OPTIMIZATION WORKSHOP (Aussois) |
Datum: | 08.01.2020 |
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 | 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 |