Lecture: Linear Orderings with several objectives: optimizing using Semidefini...
Master data
Title: | Linear Orderings with several objectives: optimizing using Semidefinite Programming |
Description: | 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. |
Keywords: | colloquium of doctoral school, multiperspective scientific exchange |
Type: | Registered lecture |
Homepage: | - |
Event: | Second status seminar (Alpen Adria Universität Klagenfurt) |
Date: | 07.10.2022 |
lecture status: | stattgefunden (Präsenz) |
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Focus of lecture |
Classification raster of the assigned organisational units:
|
Group of participants |
|
Published? |
|
working groups |
|
Cooperations
Research activities
Projects |
|
Publications | No related publications |
Events | No related events |
Lectures | No related lectures |