Seminář z aproximačních a online algoritmů
Seminar on Approximation and Online Algorithms

Petr Kolman, Morteza Monemizadeh, Jiří Sgall

Doba a místo konání [Time and place]

UMLUVENO [SCHEDULED]: v ZS 2015 se koná v pondělí [Monday] od 12:20 v S8

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese
You can subscribe to the mailing list with the seminar anouncement at

Kontakt, tel. 951 554 155;, tel. 951 554 293.

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

4. 1. 2015 (Pondělí [Monday], 12:20, MFF UK Malá Strana S8)

Martin Koutecký: Extension Complexity, MSO Logic, and Treewidth
(joint work with
Petr Kolman and Hans Raj Tiwary)

Abstract: We consider the convex hull Pφ(G) of all satisfying assignments of a given MSO formula φ on a given graph G. We show that there exists an extended formulation of the polytope Pφ(G) that can be described by f(|φ|,τ)⋅n inequalities, where n is the number of vertices in G, τ is the treewidth of G and f is a computable function depending only on φ and τ. In other words, we prove that the extension complexity of Pφ(G) is linear in the size of the graph G, with a constant depending on the treewidth of G and the formula φ. This provides a first meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs.

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

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

Cuts, hierarchical decompositions, clustering:

Vahab S. Mirrokni, Morteza Zadimoghaddam: Randomized Composable Core-sets for Distributed Submodular Maximization. STOC 2015: 153-162. Also

Harald Räcke: Optimal hierarchical decompositions for congestion minimization in networks. STOC 2008:255-264. Also here.

Jittat Fakcheroenphol, Kunal Talwar and Satish Rao: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003, J. Comput. Syst. Sci. 69(3): 485-497 (2004).

Scheduling, buffers etc.:

Yossi Azar and Oren Gilon: Buffer Management for Packets with Processing Times. ESA 2015.

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

Lin Chen, Nicole Megow and Kevin Schewior. An O(log m)-Competitive Algorithm for Online Machine Minimization. SODA 2016. Also

Other online and approximation algorithms, data structures, etc.:

Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also

Aaron Bernstein and Clifford Stein: Fully Dynamic Matching in Bipartite Graphs. ICALP 2015 (best paper). Also

Moran Feldman, Ola Svensson and Rico Zenklusen: Online Contention Resolutions Schemes. SODA 2016. Also

Mihai Patrascu, Mikkel Thorup: The Power of Simple Tabulation Hashing. J. ACM 59(3): 14 (2012). Also

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ý?)

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