Projekt: A Low-rank Approach for Solving Sparse ...
Stammdaten
A Low-rank Approach for Solving Sparse Max-Cut Problems | |
Beschreibung: | Das Max-Cut Problem ist ein NP-schweres kombinatorisches Optimierungsproblem. Die Anwendungen dieses Problems sind vielfältiger als man auf den ersten Blick glaubt, da jedes quadratische (0-1) Problem in ein Max-Cut Problem transformiert werden kann. In diesem Projekt wird eine Semidefinite Relaxierung des Max-Cut Problems betrachtet. Diese Relaxierung ist im speziellen für dünne Graphen geeignet, da sie, im Gegensatz zur SDP Relaxierung von Goemans und Williamson, nicht im Knotenraum, sondern im Kantenraum des Graphen arbeitet. Um diese SDP Relaxierung zu lösen, wird ein Algorithmus entwickelt, der auf der sogenannten Low-Rank-Methode basiert. Dabei wird die Semidefinitheitsbedingung, durch die Bedinung X=VV^t ersetzt. Derzeit kann für große Instanzen (also Graphen mit mehr als 500 Knoten) zwar die Goemans-Williamson Relaxierung gelöst werden, stärkere Relaxierungen sind jedoch nicht mehr lösbar. Mit dieser neuen Methode sollte es möglich sein, besser obere Schranken auch für Graphen jenseits von 500 Knoten berechnen zu können. |
Schlagworte: | Semidefinite Programming, Max-Cut, Nonlinear Optimization |
A Low-rank Approach for Solving Sparse Max-Cut Problems | |
Beschreibung: | The max-cut problem is one of the basic NP-hard combinatorial optimization problems and has attracted scientific interest from both the discrete and the nonlinear optimization community. In the last decade new relaxations and algorithms using semidefinite programming turned out to be particularly successful. When dealing with semidefinite programming two problems arise: 1. Finding good relaxations to the given problem and 2. Developing an algorithm for solving the semidefinite programming relaxation. This project is concerned with both questions. We investigate a semidefinite relaxation of the max-cut problem formulated in terms of the edges of the graph, thereby exploiting the (potential) sparsity of the graph. This is related to higher order liftings and can be viewed as lying 'between' the basic relaxation and the first lifting. Contrary to the basic semidefinite relaxation, which is based on the nodes of the graph, the present formulation leads to a model which is significantly more difficult to solve. To solve this problem, we develop an algorithm following a low-rank approach. This approach has been already applied to the basic max-cut relaxation and turned out to be by far the best algorithm for solving this semidefinite program. So far, for large instances, i.e., graphs with more than 500 nodes, the basic max-cut relaxation provides the best upper bounds and many of the stronger relaxations cannot be solved for instances of that size anymore. With this new algorithm we should be able to improve the upper bound for these large-scale instances significantly. |
Schlagworte: | Max-Cut, Nonlinear Optimization, Semidefinite Programming |
Kurztitel: | n.a. |
Zeitraum: | 01.06.2008 - 01.01.2009 |
Kontakt-Email: | - |
Homepage: | - |
MitarbeiterInnen
MitarbeiterInnen | Funktion | Zeitraum |
---|---|---|
Angelika Wiegele (intern) |
|
|
Zuordnung
Organisationseinheit | ||||
---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Freie Innenauftraege |
|
Kategorisierung
Projekttyp | Forschungsförderung (auf Antrag oder Ausschreibung) |
Förderungstyp | Sonstiger |
Forschungstyp |
|
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Genderrelevanz | 0% |
Projektfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Finanzierung
Förderprogramm | |||
---|---|---|---|
Forschungsrat der Alpen-Adria Universität Klagenfurt
|
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Università degli Studi di Roma “La Sapienza”
|
IT - 00185 Rom |
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte | Keine verknüpften Projekte vorhanden |
Publikationen |
|
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge |
|