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 https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.
You can subscribe to the mailing list with the seminar anouncement at https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.

Kontakt

http://kam.mff.cuni.cz/~kolman/, tel. 951 554 155;
http://iuuk.mff.cuni.cz/~sgall/, 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 http://arxiv.org/abs/1506.06715.

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 http://arxiv.org/abs/1409.0607.

Lin Chen, Nicole Megow and Kevin Schewior. An O(log m)-Competitive Algorithm for Online Machine Minimization. SODA 2016. Also http://arxiv.org/abs/1506.05721.

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

Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also http://arxiv.org/abs/1412.7693.

Aaron Bernstein and Clifford Stein: Fully Dynamic Matching in Bipartite Graphs. ICALP 2015 (best paper). Also http://arxiv.org/abs/1506.07076.

Moran Feldman, Ola Svensson and Rico Zenklusen: Online Contention Resolutions Schemes. SODA 2016. Also http://arxiv.org/abs/1508.00142.

Mihai Patrascu, Mikkel Thorup: The Power of Simple Tabulation Hashing. J. ACM 59(3): 14 (2012). Also http://arxiv.org/abs/1011.5200.

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 http://arxiv.org/abs/1307.2855.
(referuje Martin Koutecký?)


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