Original title: Algoritmy pro L-omezené toky
Translated title: Algoritmy pro L-omezené toky
Authors: Voborník, Jan ; Kolman, Petr (advisor) ; Kučera, Luděk (referee)
Document type: Master’s theses
Year: 2016
Language: eng
Abstract: [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)

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/78457

Permalink: http://www.nusl.cz/ntk/nusl-347994


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses