UNI Köln
ZAIK
INFORMATIK
IMPRESSUM
Lehrstuhl | Prof. Dr. Michael Jünger
Home
People
> Staff
> Alumni
Publications
> Articles
> Books
Teaching (german)
> Lehrveranstaltungen
> Kolloquien
Research
Where to find us

The Maxcut Problem
Begin: in the eighties
End: open
Status: ongoing
 
     
Description: > Given a graph G=(V,E), the cut associated with the node set S is the set of edges that have one endpoint in S and the other endpoint not in S. The weight of a cut is the sum of the weights of the cut edges. The maxcut problem is to find a node set S that maximises the weight of the cut. Determining a maximum cut in an arbitrary graph is an NP-hard problem. We compute a maximum cut in a graph with a branch and cut algorithm. Branch and cut has turned out to be a powerful framework for hard combinatorial optimization problems. Motivated by instances coming from Ising spin glass problems, we focus on computing maximum cuts in sparse graphs.  
     
People involved: > Michael Jünger, Frauke Liers  
       
Partners: > Miguel Anjos (University of Southampton)
Gerd Reinelt (Universität Heidelberg),
Giovanni Rinaldi (Istituto di Analisi dei Sistemi ed Informatica - CNR, Roma)
Petra Mutzel (Technische Universität Wien) 		 
     
     
Funding: Deutsche Forschungsgemeinschaft
European Comimmission (RTN ADONET 504438)

Documents:

 > Paper in the Proceedings of the SOR 1997