Home | english  | Impressum | Sitemap | KIT

Simpler and Faster Max-Cut Algorithms

Simpler and Faster Max-Cut Algorithms
Forschungsthema:Graph Algorithms

Demian Hespe, Sebastian Lamm, Matthias Mnich

Graphs have been a ubiquitous modeling tool in areas as diverse as operations research, signal processing and machine learning. Graphical representations reveal structure in the problem that is often the key to obtaining efficient algorithms for real-world data analysis problems.

As a prominent example, finding maximum cuts in graphical representations has abundant applications in machine learning, computer vision and statistical physics. However, the currently fastest algorithms for finding cuts of maximum size are either quite slow in the worst case, or complicated to implement, or give only suboptimal solutions.

A recent approach for finding maximum cuts based on kernelization was able to improve theoretical results drastically. Kernelization is a technique used to shrink a graph while preserving all information required to find an optimal solution.

The goal of this thesis is to develop a simple and practical algorithm for finding maximum cuts based on kernelization. This includes implementing and optimizing an efficient kernelization algorithm based on existing theoretical results. The resulting algorithm will be evaluated on the standard benchmark set of Biq Mac instances and compared to existing algorithms. Depending on the preferences of the candidate, one can also try new kernelization techniques to improve theoretical guarantees.

You should have:

• Interest in algorithms and data structures
• Excellent programming skills in C++
• Ability to think for yourself

INFO: This thesis is done in cooperation with the University of Bonn. Research visits are possible if desired.