magistrsko delo
Ksenija Smogavec (Avtor), Drago Bokal (Mentor)

Povzetek

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.

Ključne besede

teorija grafov;maksimalni prerez grafa;semidefinitno programiranje;hevristika;NP-polni problemi;magistrska dela;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [K. Smogavec]
UDK: 519.17(043.2)
COBISS: 20542216 Povezava se bo odprla v novem oknu
Št. ogledov: 1387
Št. prenosov: 102
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Algorithmic approach to max cut problem
Sekundarni povzetek: 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's 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.
Sekundarne ključne besede: graph theory;max cut;semidefinite programming;heuristics;NP-complete problem;master theses;
URN: URN:SI:UM:
Vrsta dela (COBISS): Magistrsko delo
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: 114 str.
ID: 8729221