The MAXCUT problem is to partition a graph's vertexes into two disjoint
subsets such that the sum of edge weights with two edge endpoints in
different subsets is maximized. The MAXCUT problem is known to be NP-hard
and has applications in various fields.
In this mini-project you will have to understand and implement a number of
deterministic heuristics and a hybrid genetic algorithm (GA) for the
problem.
The tasks are as follows:
- Read, understand and implement heuristic-approximation algorithms for
this problem such as Goemans-Williamson Algorithm, and Fiduccia-Mattheyses
algorithm.
Here is the paper.
- Implement a standard GA and a hybrid GA for the problem. The latter
algorithm is based on the paper attached.
- Compare the performance of the implemented algorithms.
- Design a GUI for running these algorithms.
- Write a comprehensive report.
This mini-project is for two SERIOUS students who will work under the
supervision of Assaf Zaritsky. The programming language is Java.
Goto mini-project home page.