Project: A Low-rank Approach for Solving Sparse ...
Master data
| A Low-rank Approach for Solving Sparse Max-Cut Problems | |
| Description: | 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. |
| Keywords: | Semidefinite Programming, Max-Cut, Nonlinear Optimization |
| A Low-rank Approach for Solving Sparse Max-Cut Problems | |
| Description: | 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. |
| Keywords: | Max-Cut, Nonlinear Optimization, Semidefinite Programming |
| Short title: | n.a. |
| Period: | 01.06.2008 - 01.01.2009 |
| Contact e-mail: | - |
| Homepage: | - |
Employees
| Employees | Role | Time period |
|---|---|---|
| Angelika Wiegele (internal) |
|
|
Assignment
| Organisational unit | ||||
|---|---|---|---|---|
|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
| Free internal orders |
|
Categorisation
| Project type | Research funding (on request / by call for proposals) |
| Funding type | Other |
| Research type |
|
| Subject areas | |
| Research Cluster | No research Research Cluster selected |
| Gender aspects | 0% |
| Project focus |
Classification raster of the assigned organisational units:
|
| working groups | No working group selected |
Funding
| Funding program | |||
|---|---|---|---|
Forschungsrat der Alpen-Adria Universität Klagenfurt
|
Cooperations
| Organisation | Address | ||
|---|---|---|---|
Università degli Studi di Roma “La Sapienza”
|
IT - 00185 Rom |
Research activities
All related research activities to this project are shown here. With the link below, you can view them in the search view where you are also able to export them.
Show related search activities in search
| Projects | No related projects |
| Publications |
|
| Events | No related events |
| Lectures |
|