|
| |
|
|
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.
|
|
|
On the Hardness of General Caching
Folwarczný, Lukáš ; Sgall, Jiří (vedoucí práce) ; Koutecký, Martin (oponent)
Cachování (také známo jako stránkování) je klasický problém modelující ob- sluhu dvouúrovňových pamět'ových systémů. Obecné cachování je varianta se stránkami různých velikostí a cen. V práci se zabýváme zpřesněním cha- rakterizace výpočetní složitosti obecného cachování v offline případě. Nedávno bylo dokázáno, že obecné cachování v offline případě je silně NP- těžké, ovšem v důkazu byly zapotřebí instance cachování se stránkami většími nežli polovina velikosti cache. Náš hlavní výsledek se vyrovnává s tímto pro- blémem: Dokazujeme, že obecné cachování je silně těžké již tehdy, když jsou velikosti stránek omezeny na {1, 2, 3}. Ve strukturální části práce pak před- stavujeme nový jednodušší důkaz úplné charakterizace work functions pomocí struktury layers v případě klasického cachování, důkaz je následně rozšířen na cachování s proměnlivou velikostí cache. Na základě těchto výsledků jsme zkonstruovali dva algoritmy pro speciální případy obecného cachování.
|
|
|
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
|
|
|
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.