|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fellows, Michael R. (oponent) ; Tantau, Till (oponent)
Tato práce podává důkaz existence kompaktních rozšířených formulací pro širokou škálu polytopů souvisejících s problémem omezujících podmínek (CSP), grafovou monadickou logikou druhého řádu (MSO) a rozšířeními MSO, mají-li dané instance omezenou stromovou šířku. Ukážeme, že naše rozšířené formulace mají další užitečné vlastnosti a odkrýváme souvislosti mezi MSO a CSP. Docházíme tak k závěru, že kombinace MSO logiky, CSP a geometrie poskytuje rozšiřitelný rámec pro konstrukci kompaktních rozšířených formulací a parametrizovaných algoritmů pro grafy s omezenou stromovou šířkou. S použitím těchto nástrojů pak zcela zodpovíme otázku parametrizované složitosti různých rozšíření MSO na dvou třídách grafů, konkrétně grafech s omezenou stromovou šířkou a s omezenou různorodostí sousedství. Objevili jsme, že (ne)linearita těchto rozšíření určuje parametrizovanou složitost na grafech s omezenou různorodostí sousedství. Na závěr studujeme tzv. posunutou kombinatorickou optimalizaci, která tvoří nelineární optimalizační rámec zobecňující standardní kombinatorickou optimalizaci. V této oblasti poskytneme prvotní zjištění z perspektivy parametrizované složitosti.
|
|
|
Toky cestami omezené délky
Altmanová, Kateřina ; Kolman, Petr (vedoucí práce) ; Pangrác, Ondřej (oponent)
V bakalářské práci se zabýváme problémem k-omezeného toku, a tedy toku, který lze dekomponovat na cesty délky nejvýše k. Podáváme přehled o známých výsledcích v této oblasti a zmiňujeme také problém k-omezeného řezu, což je množina hran z tokové sítě, která po odebrání z tokové sítě způsobí, že nee- xistuje v takto pozměněné síti k-omezený tok. Hlavním cílem práce je detailní prozkoumání článku The Maximum k-flow in a Network od autorů V. Kou- bek a A. Říha, publikovaného ve sborníku konference Mathematical Foundations of Coputer Science 1981, str. 389-397 a podání vysvětlení složitých pasáží a do- plnění vynechaných důkazů. Cíl doplnit chybějící důkazy, v této práci naplněný není. Ukázalo, že v citovaném článku mají autoři zásadní chybu. Místo doka- zování vynechaných důkazů se zaměřujeme na popsání problému, proč původní algoritmus nefunguje. 1
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent)
Abstrakt. Práce se věnuje problému preemptivního online rozvrhování paralelních úloh. Podává přehled předchozích výsledků pro tento problém. Pro některé speciální varianty problému, například pro úlohy na jeden a dva procesory, poskytuje nové výsledky, jak v podobě dolních odhadů, tak v podobě kompetitivních algoritmů. Je objevena chyba v dříve publikovaném dolním odhadu a opravena na správný dolní odhad. Je navržen algoritmus pro verzi problému se čtyřmi procesory a s úlohami na jeden a dva procesory, pro který je vyslovena hypotéza, že dosahuje nejlepšího možného kompetitivního poměru.
|
|
| |
|
|
Approximation and Online Algorithms
Tichý, Tomáš ; Sgall, Jiří (vedoucí práce) ; Kolman, Petr (oponent) ; van Stee, Rob (oponent)
This thesis presents results of our research in the area of optimization problems with incomplete information-our research is focused on the online scheduling problems. Our research is based on the worst-case analysis of studied problems and algorithms; thus we use methods of the competitive analysis during our research. Althrough there are many "real-world" industrial and theoretical applications of the online scheduling problems there are still so many open problems with so simple description. Therefore it is important, interesting and also challenging to study the online scheduling problems and their simplified variants as well. In this thesis we have shown the following our results of our research on the online scheduling problems: A 1.58-competitive online algorithm for the problem of randomized scheduling of unit jobs on a single processor, where the jobs are arriving over time and the total weight of processed jobs ismaximized. A lower bound 1.172 on the competitive ratio for the problem of randomized scheduling of 2-uniform unit jobs on a single processor, where the jobs are arriving over time andthe totalweight of processed jobs is maximized. A lower bound 1.25 on the competitive ratio for the problem of randomized scheduling of s-uniform unit jobs on a single processor where s is tending to...
|
|
|
Algoritmy pro L-omezené toky
Voborník, Jan ; Kolman, Petr (vedoucí práce) ; Kučera, Luděk (oponent)
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)
|
|
|
Obtížné problémy vzhledem k parametru různorodost sousedství
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fiala, Jiří (oponent)
Parametrizovaná složitost je oblast teoretié informatiky zabývající se výpočetní složitostí pro- blémů měřenou nikoliv pouze délkou vstupu, ale i nějakým jeho parametrem. "Různorodost soused- ství" je nový strukturální parametr grafu, který je atraktivní především proto, že pro grafy s pevnou různorodostí sousedství se stávají efektivně řešitelnými i některé problémy, jež zůstávají těžké pro jiné parametry s různorodostí sousedství neporovnatelnými. V této práci nově ukazujeme efektivní řeši- telnost vzhledem k různorodosti sousedství pro tři problémy těžké vzhledem ke stromové šířce. To tvoří hlavní část této práce a jedná se o náš vlastní výzkum. Dále pak práce obsahuje přehled další zajímavý problémů a také shrnutí současného stavu v oblasti parametrů pro řídké a husté grafy. 1
|
|
|
Algoritmy pro řezy v grafech
Pecsők, Ján ; Kolman, Petr (vedoucí práce) ; Tiwary, Hans Raj (oponent)
Problémy hledání řezu v grafu mohou být popsány jako problémy, v kterých jsme žádáni rozdělit graf na 2 nebo více částí. V této práci podáváme přehled metod a konceptů používaných při hledání nejlepších řezů vzhledem k několika kritériím. Dokážeme dualitu mezi problémem hledání multi-komoditního toku a řídkého řezu z práce autorů Leighton a Rao (LR). Dokážeme ji pomocí algoritmu užívajícího lineárního programování a geometrického vnořování. Následně představíme práci autorů Arora, Rao a Vazirani (ARV) a jejich algoritmus založený na semidefinitním programování a také na geometrickém vnořování. Též vysvětlíme koncept expanzních toků poprvé představených v práci ARV. Další rozsáhlá sekce je věnovaná spektrální teorii. Prvky spektrální teorie a koncept expanzních toků se spojí v kapitole o algoritme využívajícího jednokommoditní toky. Nakonec ukážeme výsledky naši implementace varianty algoritmu využívajícího jednokomoditní toky a algoritmu vnořování dle LR. Powered by TCPDF (www.tcpdf.org)
|
|
|
Toky a cesty s omezením
Knop, Dušan ; Kolman, Petr (vedoucí práce) ; Krčál, Marek (oponent)
Název práce: Toky a cesty s omezením Autor: Dušan Knop Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: Doc. Mgr. Petr Kolman, PhD, Katedra aplikované matematiky Abstrakt: V předložené práci studujeme problém délkou omezených řezů mezi dvojicí vr- cholů grafu. V tomto problému je cílem odebrat hrany z grafu tak, aby po jejich odebrání měla předem specifikovaná dvojice vrcholů předepsanou vzdálenost. Práce poskytuje přehled o základní literatuře o tomto problému a prezentuje souvislosti s jinými problémy. V rámci tohoto také nabízí mnoho aplikací délkou omezených toků a řezů. Pro tento NP-těžký problém popisuje heuristiky pro redukci dat. Hlavním výsledkem práce pak je polynomiální algoritmus pro sériově-paralelní grafy. Klíčová slova: řezy, sériově-paralelní grafy, algoritmus, složitost
|
|
|
Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Kráľ, Daniel (oponent)
Courcellova věta mluví o výpočetní složitosti rozhodovacích problémů defino- vaných formulemi monadické logiky druhého řádu nad relačními strukturami s omezenou stromovou šířkou. Pro pevnou stromovou šířku a vstupní formuli dává Courcellova věta algoritmus, který formuli rozhodne v lineárním čase nad strukturou dané stro- mové šířky. Práce podává samostatný důkaz Courcellovy věty pomocí metod teorie konečných modelů. Dále obsahuje důkazy všech potřebných prerekvizit hlavního důkazu, zejména v teorii konečných modelů široce využívané Ehrenfeuchtovy-Fraïssého věty. Práce též obsahuje implementaci algoritmu plynoucího z tohoto důkazu. Nakonec nastiňuje aktuální stav výzkumu dané oblasti a z něj plynoucí možnosti. 1
|
host ::
RSS.