|
|
Heuristics for Length Bounded Cuts
Madaj, Pavel ; Kolman, Petr (vedoucí práce) ; Koutecký, Martin (oponent)
Táto práca sa zaoberá problémom nájdenia minimálneho dľžkovo obmedzeného rezu v grafe. Najprv poskytneme stručný prehľad problému a jeho aplikácií. Potom zhrnieme známe teoretické výsledky a aproximačné algoritmy. Skúmame existujúce formulácie li- neárnych programov pre tento problém a navrhujeme novú. Stručná diskusia o potenciál- nych ťažkých príkladoch, ktoré sú využité na testovanie našich formulácií, je tiež zahrnutá. Zameriavame sa na správanie našej navrhovanej rodiny lineárnych programov a porovná- vame ju s existujúcou prirodzenou formuláciou. Taktiež porovnávame výkonnosť rôznych heuristík a aproximačných algoritmov v praxi skúmaním ich správania sa na veľkej sade malých instancií. 1
|
|
|
A Framework For Experimental Evaluation of Opinion Diffusion Models
Jelínek, Dominik ; Koutecký, Martin (vedoucí práce) ; Vetta, Adrian (oponent)
Title: A Framework for Experimental Study of Opinion Diffusion Models Author: Dominik Jelínek institute: IUUK Supervisor: Martin Koutecký, IUUK Abstract: Our theoretical contribution centers on defining possible diffusion steps decreasing either Kendall-tau or Spearman's footrule distance between two bucket orders, which are orders with ties. These diffusion steps give us a new ability to work with, among others, election data where voters can specify any number of top preferences. From the practical contribution, we have developed an experimental framework specialized for working with bucket orders. The framework's easily extendable architecture provided by the usage of strategy design pattern allows for the generation and comparison of various models at a large scale. A part of a framework is an extensive list of important metrics and visualization techniques to observe and compare the behavior of different models. Keywords: bucket order, diffusion model, social network, framework, election iii
|
|
| |
|
|
Performance Comparison of ILP versus Logical Solvers on Bribery-type Problems
Kumar, Aryan ; Koutecký, Martin (vedoucí práce) ; Faliszewski, Piotr (oponent)
Celočíselné lineární programování (ILP) se ukázalo být mocným nástro- jem pro řešení obtížných problémů, zejména v oblasti výpočetní sociální volby, kde byl použit k řešení variant problému úplatků. V tomto prob- lému jde o nalezení nejmenší změny, která vede ke kýženému výsledku po- tom, co ve společnosti proběhne proces šíření názorů. Předchozí experimenty ukazují, že řešení tohoto problému pomocí ILP je omezené pouze na malé instance. Novější výsledky ukazují, že tentýž problém lze vyjádřit pomocí logických formulí v Presburgerově aritmetice (PrA) a lze tak dosáhnout složi- tosti podobné algoritmu ILP. Proto se nabízí provést praktickou analýzu přístupu založeného na PrA. V tomto projektu jsme vygenerovali náhodné instance s předepsanými parametry voleb a modelovali je jako instance ILP a PrA. Následně jsme takto získané instance vyřešili pomocí řešičů jako jsou např. GUROBI, GLPK a Z3 a provedli jsme srovnávací studii k vyhodnocení výkonnosti obou přístupů vzhledem k různých parametrům, jako jsou např. počet typů voličů a difúzních kroků. Naše výsledky ukazují, že přístup skrze ILP je v praxi robustnější než přístup PrA. 1
|
|
|
Experimentální analýza simplexové metody na problému multikomoditního toku
Kubek, Dávid ; Koutecký, Martin (vedoucí práce) ; Borgwardt, Steffen (oponent)
Tato práce se zabývá problémem multikomoditního toku minimální ceny (MMCF). Naším cílem je přispět k hledání kombinatorického algoritmu pro MMCF. Použili jsme simplexovou metodu k experimentálnímu prozkoumání vrcholů polyedru přípustných řešení na sadě veřejně dostupných instancí MMCF. K dosažení tohoto cíle jsme vyvinuli řešič, který je schopen sledovat řešení v každé iteraci algoritmu v přesné aritmetice; tato funkcionalita ne- byla k dispozici v existujících řešičích. Zaměřujeme se na zlomkovost MMCF instancí a vliv volby pivotovacího pravidla, zejména zda je zlomkovost expo- nenciální nebo polynomiální s ohledem na rostoucí dimenzi problému. Naše zjištění naznačují, že zlomkovost vykazuje exponenciální chování.
|
|
|
A Symmetric Homophily-preserving Opinion Diffusion Model
Prokop, Aleš ; Koutecký, Martin (vedoucí práce) ; Talmon, Nimrod (oponent)
Definujeme a studujeme symetrický a homofilii zachovávající model šíření názorů na skupinách voličů. Tento model je symetrický, což znamená, že se skupiny voličů ovlivňují navzájem. Tento model také zachovává homofilii, tedy pokud volič změní svůj názor, tak se spolu s tím změní jeho okolí, což je často pozorovaná vlastnost sociálních sítí. Uvádíme vlastnosti našeho modelu šíření názorů, mezi které patří konvergence, ϵ-konvergence na některých typech grafů, dále také polyedrický popis množiny pevných bodů a zobecnění procesu na grafy s váženými hranami a orientované grafy společně s jejich vlastnostmi. Poskytujeme definici prahové verze našeho šíření názorů. Studujeme pevné body difuze a prahové difuze. Také poskytujeme program pro experimentování na našem modelu. 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
|
|
|
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í.
|
|
|
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.