Diplomová práce se zabývá využitím semidefinitního programování v kombinatorické optimalizaci. V první části je shrnuta teorie, která je potřebná k práci v této oblasti. V části druhé se zabýváme Shannonovou kapacitou grafu, Lovászovou θ funkcí a úlohou maximálního řezu. Zmíněné algoritmy jsou implementovány a testovány v programovacím jazyce Python 3.
Annotation in English
Thesis deals with semidefinite programming in combinatorial optimization. The first part is summarizes the theory needed to work in this field. In the second section we are dealing with Shannon capacity of the graph, Lovasz θ function, and with MAX CUT problem. The mentioned algorithms are implemented and tested in the Python 3 programming language.
Keywords
kombinatorická optimalizace, semidefinitní programování, aproximační algoritmus, vektorové programování, Shannonova kapacita grafu, Lovászova theta funkce, MAX CUT, MAX k-CUT, kapacitní MAX k-CUT
Keywords in English
combinatorial optimization, semidefinite programming, vector programming, approximation algorithm, Shannon capacity of the graph, Lovasz theta function, MAX CUT, MAX k-CUT, capacited MAX k-CUT
Length of the covering note
57
Language
CZ
Annotation
Diplomová práce se zabývá využitím semidefinitního programování v kombinatorické optimalizaci. V první části je shrnuta teorie, která je potřebná k práci v této oblasti. V části druhé se zabýváme Shannonovou kapacitou grafu, Lovászovou θ funkcí a úlohou maximálního řezu. Zmíněné algoritmy jsou implementovány a testovány v programovacím jazyce Python 3.
Annotation in English
Thesis deals with semidefinite programming in combinatorial optimization. The first part is summarizes the theory needed to work in this field. In the second section we are dealing with Shannon capacity of the graph, Lovasz θ function, and with MAX CUT problem. The mentioned algorithms are implemented and tested in the Python 3 programming language.
Keywords
kombinatorická optimalizace, semidefinitní programování, aproximační algoritmus, vektorové programování, Shannonova kapacita grafu, Lovászova theta funkce, MAX CUT, MAX k-CUT, kapacitní MAX k-CUT
Keywords in English
combinatorial optimization, semidefinite programming, vector programming, approximation algorithm, Shannon capacity of the graph, Lovasz theta function, MAX CUT, MAX k-CUT, capacited MAX k-CUT
Research Plan
Semidefinitní programování (SDP) se jako nástroj výzkumu objevuje v kombinatorické
optimalizaci převážně v oblasti barvení grafů, studia řezů grafů, nezávisloti a
Shannonovy kapacity. Cílem práce je přehledné zpracování těchto oblastí s
přihlédnutím k příslušným algoritmům řešení úloh SDP a dále práce na vybraném problému.
Research Plan
Semidefinitní programování (SDP) se jako nástroj výzkumu objevuje v kombinatorické
optimalizaci převážně v oblasti barvení grafů, studia řezů grafů, nezávisloti a
Shannonovy kapacity. Cílem práce je přehledné zpracování těchto oblastí s
přihlédnutím k příslušným algoritmům řešení úloh SDP a dále práce na vybraném problému.
Recommended resources
S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, ISBN-13:978-0521833783, 2005.
L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Review, 38(1), 49-95, 1996.
M.X. Goemans: Semidefinite Programming and Combinatorial Optimization, Documenta Mathematica, Extra Volume ICM 1998 (III), 657-666.
L. Lovász, Semidefinite Programs and Combinatorial Optimization. In: Reed B.A., Sales C.L. (eds)
Recent Advances in Algorithms and Combinatorics. CMS Books in Mathematics/Ouvrages de mathématiques de la SMC. Springer, New York, NY, 2003.
Recommended resources
S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, ISBN-13:978-0521833783, 2005.
L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Review, 38(1), 49-95, 1996.
M.X. Goemans: Semidefinite Programming and Combinatorial Optimization, Documenta Mathematica, Extra Volume ICM 1998 (III), 657-666.
L. Lovász, Semidefinite Programs and Combinatorial Optimization. In: Reed B.A., Sales C.L. (eds)
Recent Advances in Algorithms and Combinatorics. CMS Books in Mathematics/Ouvrages de mathématiques de la SMC. Springer, New York, NY, 2003.