Vortrag: Linear Orderings with several objectives: optimizing using Semidefini...
Stammdaten
Titel: | Linear Orderings with several objectives: optimizing using Semidefinite Programming |
Beschreibung: | The Cutwidth Minimization Problem is a linear ordering problem on graphs, whose applications include natural language processing, information retrieval, graph drawing, and network migration scheduling. Finding the minimum cutwidth of a graph is an NP-hard problem, for which several heuristics and metaheuristics have been designed in order to compute upper bounds. Regarding lower bounds, integer linear programming models have been proposed, some with very good results on sparse graphs. However, even the best approaches see their performances decrease with the density and the size of the instances. In this talk, we introduce a new semidefinite relaxation for the Cutwidth Minimization Problem and investigate ways to efficiently strengthen it, using different sets of valid inequalities. We develop a cutting-plane algorithm based on these improved semidefinite relaxations, allowing us to significantly improve lower bounds for dense graphs. These methods can then be used for other challenging problems related to finding linear orderings minimizing other graph parameters, such as the pathwidth or the bandwidth. |
Schlagworte: | colloquium of doctoral school, multiperspective scientific exchange |
Typ: | Angemeldeter Vortrag |
Homepage: | - |
Veranstaltung: | Second status seminar (Alpen Adria Universität Klagenfurt) |
Datum: | 07.10.2022 |
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 |