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
angelika.wiegele@aau.at
Institut für Mathematik
Forschungsaktivitäten
zur Visitenkarte
(intern)
  • Projektleiter/in
  • Kontaktperson
  • Antragsteller/in
  • 01.06.2008 - 01.01.2009
  • 01.06.2008 - 01.01.2009
  • 01.06.2008 - 01.01.2009

Zuordnung
Organisationseinheit
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation
Freie Innenauftraege
  • AFR87500003

Kategorisierung
Projekttyp Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp Sonstiger
Forschungstyp
  • Angewandte Forschung
  • Grundlagenforschung
Sachgebiete
  • 11 - Mathematik, Informatik *
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz 0%
Projektfokus
  • Science to Science (Qualitätsindikator: n.a.)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Finanzierung
Förderprogramm
Forschungsrat der Alpen-Adria Universität Klagenfurt
Organisation: Forschungsrat der Alpen-Adria Universität Klagenfurt

Kooperationen
Organisation Adresse
Università degli Studi di Roma “La Sapienza”
Piazzale Aldo Moro 5
00185 Rom
Italien - restliches Italien
Piazzale Aldo Moro 5
IT - 00185  Rom