Název: Algoritmy pro L-omezené toky
Překlad názvu: Algoritmy pro L-omezené toky
Autoři: Voborník, Jan ; Kolman, Petr (vedoucí práce) ; Kučera, Luděk (oponent)
Typ dokumentu: Diplomové práce
Rok: 2016
Jazyk: eng
Abstrakt: [eng] [cze]
We study the problem of maximum $L$-bounded flow, a flow decomposable to flow paths of length bounded by $L$. We review the basic results and related problems. Maximum $L$-bounded flow can be computed in polynomial time in networks with unit edge lengths but combinatorial algorithm is not known. We study combinatorial approach to this question. In networks with general edge lengths, the problem is \cNP-hard; for this problem we describe a fully polynomial approximation scheme (FPTAS) based on an algorithm for maximum multicommodity flow. This approach is practically more efficient than the previous FPTAS which was based on the ellipsoid method. Powered by TCPDF (www.tcpdf.org) V práci zkoumáme problém maximálního $L$-omezeného toku, tedy toku, který lze rozložit na tokové cesty délky nejvýš $L$. Podáváme přehled o základních výsledcích a prezentujeme souvislosti s jinými problémy. Maximální $L$-omezený tok lze řešit v polynomiálním čase v sítích s jednotkovými délkami hran pomocí lineárního programování, ale kombinatorický algoritmus není znám. Práce studuje kombinatorický přístup k této otázce. V~sítích s obecnými délkami hran je problém \cNP-těžký, pro tento případ popisujeme kombinatorické plně polynomiální aproximační schéma (FPTAS) založené na algoritmu pro maximální multikomoditní tok. Tento přístup je prakticky efektivnější než dřívější FPTAS, který využíval elipsoidovou metodu. Powered by TCPDF (www.tcpdf.org)

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/78457

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-347994


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce