|
|
Combinatorial Algorithms for Flow Problems
Hladík, Richard ; Koutecký, Martin (vedoucí práce) ; Vegh, Laszlo (oponent)
Problém multikomoditního toku (MCF) a problém K-omezeného toku (LBF) jsou dvě zobecnění problému maximálního toku. Oba problémy jdou řešit pomocí lineárního programování a aproximovat plně polynomiálními aproximačními schématy (FPTAS). Není však pro ně znám žádný algoritmus, který je zároveň 1) exaktní, 2) polynomiální a 3) kombinatorický a/nebo nepoužívající obecné metody jako lineární programování. O multikomoditním toku se někdy mluví jako o "nejsnazším problému, který nemá kombi- natorický algoritmus". V této práci shrnujeme specializované i obecné metody pro řešení obou problémů. Přinášíme dva nové kombinatorické algoritmy, první založený na metodě Frank-Wolfe pro konvexní optimalizaci (pro MCF i LBF), druhý založený na most helpful cycle cancelling (pro MCF), a dokazujeme, že v sítích s polynomiálními poptávkami oba algoritmy běží v čase poly(délka vstupu, 1/ε). Také přinášíme výsledky v polyhedrální teorii, zejména v souvislosti s kružnicemi MCF- a LBF-mnohostěnů. Na jednu stranu dokazujeme, že existence množiny zobecňující množinu kružnic sestávající se pouze z vektorů malé normy by už zaručila "skoro-exaktnost" obou algoritmů (resp. konvergenci v ‰(log 1/ε) krocích). Na druhou stranu dokazujeme existenci exponenciálně velkých kružnic pro MCF i LBF. Existence množiny zobecňující množinu kružnic jiné...
|
host ::
RSS.