Algorithmic approach to max cut problem

Problem maksimalnega prereza grafa je najti takšno razbitje množice vozlišč grafa, da bo vsota uteži na povezavah, ki povezujejo ta dva kosa razbitja, največja. Problem maksimalnega prereza je NP-poln in je eden izmed osnovnih 21-ih Karpovih problemov. Zaradi njegove teoretične in praktične pomembnosti, aplikacije ima v statistični fiziki in vezjih, je bilo zapisanih že kar nekaj različnih aproksimacijskih algoritmov, hevristik ali kombinacij optimizacijskih metod in hevristik, ki rešujejo problem maksimalnega prereza. V magistrskem delu predstavimo problem maksimalnega prereza na posebnih razredih grafov, na katerih lahko najdemo rešitev problema v polinomskem času. Tretje poglavje je namenjeno Goemans Williamsonovemu aproksimacijskemu algoritmu, ki s pomočjo semidefinitnega programa najde rešitev, katere garantirana vrednost je vsaj 87 % optimalne rešitve in predstavlja prelom na področju aproksimacijskih algoritmiov. Poleg njunega algoritma predstavimo še Biq Mac algoritem, ki doseže skoraj optimalne rešitve za grafe z n ≤ 100, in dualno skaliran algoritem, ki je primeren tudi za velike redke grafe. Temu sledi predstavitev posplošitve Goemans Williamsonovega algoritma za maksimalen k-prerez. Nazadnje predstavimo še nekaj hevristik, ki so učinkovite pri iskanju maksimalnega prereza.Max cut problem consists of partitioning the vertices of undirected weighted graph into two subsets, such that the sum of the weights of the edges that connect vertices in different partitions is maximized. Max cut problem is NP-complete and is one of Karp\u27s 21 problems. Because of its theoretical and practical importance, applications in statistical physics and circuit layout design, various approximation algorithms, heuristics or combinations of optimization and heuristics methods have been developed to solve max cut problem. In this master thesis we describe max cut problem on classes of graphs for which max cut is solvable in polynomial time. Third chapter presents Goemans Williamson approximation algorithm that uses semidefinite programming and provides result of which expected value is at least 87 % times of optimal solution and presents break-through in field of approximation algorithms. We also present Biq Mac algorithm, which can obtain nearly optimal solutions for graphs with n ≤ 100, and dual scaling algorithm, which has been used to solve large scale semidefinite programs. Additionally a generalised Goemans Williamson algorithm for max k-cut is given. The final chapter presents some heuristics that are efficient in solving max cut problem