Projekt: Lasserre-Hierarchie für Max-Cut: eine A...
Stammdaten
| Lasserre-Hierarchie für Max-Cut: eine Annäherung | |
| Beschreibung: | x |
| Schlagworte: | Max-Cut Problem; Lasserre Hierarchie; Kombinat. Optimierung |
| Lasserre hierarchy for max-cut from a computational point of view | |
| Beschreibung: | The max-cut problem is one of the classical NP-complete problems defined on graphs. SDP-relaxations turned out to be in particular successful on these problems. Beside the basic semidefinite relaxation (underlying the Goemans-Williamson hyperplane rounding algorithm) and tightenings of this relaxation, iterative approaches exist that converge towards the cut polytope. Such a systematic hierarchy was introduced by Lasserre. The first relaxation in this hierarchy coincides with the basic SDP relaxation. Due to the high computational cost, already the second relaxation in this Lasserre-hierarchy is intractable for small graphs. We investigate an iterative algorithm for computing a strengthened SDP-relaxation towards this second relaxation combined with constraints from the metric polytope. This can also be viewed as a strengthening of the basic SDP relaxation using semidefinite cuts. Theoretical facts and computational results will be exploited in order to evaluate the new algorithm. |
| Schlagworte: | max-cut problem; Lasserre hierarchy; combinat. optimization |
| Kurztitel: | n.a. |
| Zeitraum: | 01.04.2012 - 01.01.2014 |
| Kontakt-Email: | - |
| Homepage: | - |
MitarbeiterInnen
| MitarbeiterInnen | Funktion | Zeitraum |
|---|---|---|
| Franz Rendl (intern) |
|
|
| Angelika Wiegele (intern) |
|
|
Zuordnung
| Organisationseinheit | ||||
|---|---|---|---|---|
|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Kategorisierung
| Projekttyp | laufender Arbeitsschwerpunkt |
| Förderungstyp | Sonstiger |
| Forschungstyp |
|
| Sachgebiete | |
| Forschungscluster | Kein Forschungscluster ausgewählt |
| Genderrelevanz | 0% |
| Projektfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
| Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Finanzierung
Keine Förderprogramme vorhanden
Kooperationen
| Organisation | Adresse | ||
|---|---|---|---|
Ecole Polytechnique de Montreal
|
CA - H3T 1J4 Montreal |
Forschungsaktivitäten
Hier werden alle mit diesem Projekt in Zusammenhang stehenden Forschungsaktivitäten angezeigt. Mit dem untenstehenden Link können sie sich diese Forschungsaktivitäten in der Suche anzeigen lassen und gegebenenfalls exportieren.
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Zugehörige Forschungsaktivitäten in der Suche anzeigen
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
| Projekte | Keine verknüpften Projekte vorhanden |
| Publikationen | Keine verknüpften Publikationen vorhanden |
| Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
| Vorträge |
|