| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Paralelni razveji in omeji algoritem BiqMac Solver
Authors:ID Vegi Kalamar, Alen (Author)
ID Bokal, Drago (Mentor) More about this mentor... New window
ID Povh, Janez (Co-mentor)
Files:.pdf MAG_Vegi_Kalamar_Alen_2018.pdf (908,74 KB)
MD5: 338C602AD68962F3C0520255B5BECE72
PID: 20.500.12556/dkum/4451034a-5bb3-4108-b601-98cac3e1fa96
 
Language:Slovenian
Work type:Master's thesis/paper (mb22)
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Problem maksimalnega prereza je primer NP težkega problema. To pomeni, da ne poznamo učinkovitega polinomskega algoritma za reševanje problema za poljuben graf in domnevamo, da tudi ne obstaja. Kljub temu obstajajo pristopi, kako reševati problem do optimalnosti. V kolikor poznamo učinkovite hevristike in poenostavitve problema, je primeren pristop algoritem razveji in omeji. Rendl, Rinaldi in Wiegele so z uporabo različnih poenostavitev, dualne teorije, aproksimacijskih algoritmov in hevristik razvili učinkovit algoritem razveji in omeji z imenom BiqMac Solver, ki optimalno reši problem maksimalnega prereza tudi za večje grafe. Zaradi strukture je algoritem primeren, da ga implementiramo za paralelno izvajanje. Namen magistrskega dela je predstavitev algoritma BiqMac in njegova paralelna implementacija.
Keywords:maksimalen prerez grafa, semidefinitno programiranje, hevristike, algoritem razveji in omeji, paralelno računanje
Year of publishing:2018
Publisher:[A. V. Kalamar]
Source:Maribor
PID:20.500.12556/DKUM-72022 New window
UDC:519.178:004.421(043.2)
COBISS.SI-ID:24058120 New window
NUK URN:URN:SI:UM:DK:AU08UJQE
Publication date in DKUM:04.10.2018
Views:1137
Downloads:144
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
  
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.

Licences

License:CC BY-SA 4.0, Creative Commons Attribution-ShareAlike 4.0 International
Link:http://creativecommons.org/licenses/by-sa/4.0/
Description:This Creative Commons license is very similar to the regular Attribution license, but requires the release of all derivative works under this same license.
Licensing start date:06.09.2018

Secondary language

Language:English
Title:Parallel branch and bound BiqMac Solver Algorithm
Abstract:The max cut problem is a NP hard problem. That means that no effective algorithm for this problem is known, and it is conjectured that none exists. However, there are a few possible methods of optimally solving these problems. If the efficient heuristics and relaxations of the problem are known, a correct procedure is using a branch and bound algorithm. Using various relaxations, duality theory, approximation algorithms and heuristics, Rendl, Rinaldi and Wiegele developed an effective branch and bound algorithm called BiqMac Solver, which optimally solves max cut problems, even for large graphs. Because of its structure, the algorithm is appropriate for parallel computing. The purpose of this master’s thesis is to present the BiqMac algorithm and its parallel implementation.
Keywords:max cut, semidefinite programming, heuristics, branch and bound algorithm, parallel computation


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