| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Algoritmični pristopi k problemu maksimalnega prereza grafov
Authors:ID Smogavec, Ksenija (Author)
ID Bokal, Drago (Mentor) More about this mentor... New window
Files:.pdf MAG_Smogavec_Ksenija_2014.pdf (2,88 MB)
MD5: 33B635AD38E31C8C1CF92F1A8EF34BA7
 
Language:Slovenian
Work type:Master's thesis (m2)
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract: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.
Keywords:maksimalen prerez grafa, semidefinitno programiranje, hevristika, NP-poln problem
Year of publishing:2014
Publisher:[K. Smogavec]
Source:Maribor
PID:20.500.12556/DKUM-44031 New window
UDC:519.17(043.2)
COBISS.SI-ID:20542216 New window
NUK URN:URN:SI:UM:DK:VUWAJUW2
Publication date in DKUM:21.05.2014
Views:1578
Downloads:134
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
Kopiraj citat
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:Algorithmic approach to max cut problem
Abstract: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.
Keywords:max cut, semidefinite programming, heuristics, NP-complete problem


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica