Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Doba a místo konání

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese

Kontakt, tel. 221 914 155;, tel. 221 914 293.

Nejbližší program semináře [Next program]

5. 1. 2015 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Martin Koutecký: Extended Formulation for Binary CSP that is Compact for Instances of Bounded Treewidth

Abstract: An instance of a binary CSP problem consists of a set of variables, its domains, and a set of constraints, which are binary relations on variables. A graph of an instance is a graph whose vertices are the variables and where two vertices share an edge if the instance contains a constraint over correspoding variables. A binary CSP instance has bounded treewidth if its graph has bounded treewidth. We present an LP formulation of the polytope of all assignemets of a binary CSP instance with bounded treewidth of size |D|^tw (where D is the union of all domains and tw is the treewidth of the instance). This allows one to optimize over (for example) the number of violated constraints. The Binary CSP problem generalizes several important combinatorial optimization problems, for most of which a compact extended formulation was not previously known.

Předběžný další program [Preliminary future program]

Další články pro ZS 2014 [More papers proposed for this semester]

Andreas Björklund and Thore Husfeldt: Shortest Two Disjoint Paths in Polynomial Time. ICALP 2014 (best paper award).

Yann Disser and Martin Skutella: The Simplex Algorithm is NP-mighty. SODA 2015. Also

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also

Gábor Braun, Sebastian Pokutta: The matching polytope does not admit fully-polynomial size relaxation schemes. SODA 2015. Also

Alantha Newman: An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs. ESA 2014. Also

Guru Guruganesh, Laura Sanita, Chaitanya Swamy: Region-Growing and Combinatorial Algorithms for k-Route Cut Problems. (k dispozici mailem)

Samozřejmě, jako vždy, jsou vítany jsou i další náměty, zejména pak prezentace vlastních výsledků účastníků semináře.

Další články, o kterých jsme uvažovali, zbylé z minulého semestru atd.
[Additional proposed papers, leftovers from the last semester]

Lorenzo Orecchia, Zeyuan Allen Zhu: Flow-Based Algorithms for Local Graph Clustering. SODA 2014. Also
(referuje Martin Koutecký?)

Marcin Mucha and Maxim Sviridenko: No-Wait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem. ICALP 2013. Also

Martin Aumuller and Martin Dietzfelbinger:  Optimal Partitioning for Dual Pivot Quicksort. ICALP 2013. Also and slides.

Susanne Albers, Matthias Hellwig: Semi-online scheduling revisited. Theor. Comput. Sci. 443: 1-9 (2012).

Chandra Chekuri, Alina Ene: Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. SODA 2013.

Hyung-Chan An, Robert Kleinberg, David B. Shmoys: Improving Chrisofides' Algorithm for the s-t Path TSP. STOC 2012.

Subash Khot: On the Unique Games Conjecture. In Proc. 25th Complexity (CCC), 99-121, 2010.

Luca Trevisan: On Khot's unique games conjecture. Bull. Amer. Math. Soc. 49 (2012), 91-111.

Předchozí program semináře [Past program]