Vortrag: An exact solution method for the Max-Cut problem

Stammdaten
Titel: An exact solution method for the Max-Cut problem
Beschreibung: In this talk we present a method for finding exact solutions of the Max-Cut problem $\max x^{T}Lx \mbox{ such that } x \in \{\pm 1\}^{n}.$ We use a branch and bound setting, that applies a dynamic version of the bundle method as bounding routine. This dynamic bundle uses Lagrangian duality to obtain a "nearly optimal" and "nearly feasible" solution of the basic semidefinite Max Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic SDP relaxation of the Max Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to unconstrained quadratic 0-1 problems and to instances of the graph bisection problem. The experiments show, that our method nearly always outperforms all other approaches. In particular, where LP based methods fail (i.e. dense graphs) our method performs very well. Exact solutions are obtained in reasonable time for any instance of size up to $n=100$, no matter what density; for sparse graphs we can solve even larger problem classes
Schlagworte:
Typ: Gastvortrag
Homepage: -
Veranstaltung: -
Datum: 19.04.2006
Vortragsstatus:
Ort: IASI-CNR, Rom
Staat:

Beteiligte
Angelika Wiegele
angelika.wiegele@aau.at
Institut für Mathematik
Forschungsaktivitäten
zur Visitenkarte
(intern)
  • Vortragende/r

Zuordnung
Organisation Adresse
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
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Kategorisierung
Sachgebiete
  • 1104 - Angewandte Mathematik
Forschungscluster Kein Forschungscluster ausgewählt
Vortragsfokus
  • Science to Science (Qualitätsindikator: n.a.)
Klassifikationsraster der zugeordneten Organisationseinheiten:
TeilnehmerInnenkreis Kein TeilnehmerInnenkreis ausgewählt
Publiziert?
  • Nein
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Kooperationen
Keine Partnerorganisation ausgewählt