Title: Semidefinitní programování v kombinatorické optimalizaci
Other Titles: Semidefinite programming in combinatorial optimization
Authors: Špaček, Ondřej
Advisor: Čada Roman, Doc. Ing. Ph.D.
Referee: Kaiser Tomáš, Prof. RNDr. DSc.
Issue Date: 2020
Publisher: Západočeská univerzita v Plzni
Document type: diplomová práce
URI: http://hdl.handle.net/11025/55395
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 different language: 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
Abstract: 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 $\vartheta$ funkcí a úlohou maximálního řezu. Zmíněné algoritmy jsou implementovány a testovány v programovacím jazyce Python 3.
Abstract in different language: 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 $\vartheta$ function, and with MAX CUT problem. The mentioned algorithms are implemented and tested in the Python 3 programming language.
Rights: Plný text práce je přístupný bez omezení
Appears in Collections:Diplomové práce / Theses (KMA)

Files in This Item:
File Description SizeFormat 
diplomova_prace.pdfPlný text práce1,39 MBAdobe PDFView/Open
PO_Spacek.pdfPosudek oponenta práce738,2 kBAdobe PDFView/Open
PV_Spacek.pdfPosudek vedoucího práce632,73 kBAdobe PDFView/Open
P_Spacek.pdfPrůběh obhajoby práce158,51 kBAdobe PDFView/Open
dp_ospacek.zipVŠKP - příloha1,93 MBZIPView/Open


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/55395

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.