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

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: v LS 2015 se koná v pondělí od 10:40 v S8

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

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

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

30. 3. 2015 (Pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Nikhil Bansal: Approximating independent sets in sparse graphs. SODA 2015.
(referuje Martin Böhm)

Abstract: We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d / log d) approximation due to Halperin. It is also known that no o(d / log^2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results:
(i) The natural LP formulation for the problem strengthened by O(log^4 d) levels of the mixed-hierarchy has an integrality gap of O~(d / log^2 d), where O~() ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a O~(d / log2 d) approximation algorithm with sub-exponential running time.
(ii) We give an O(d / log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in n^O(1) exp(log^O(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdos, Komlos and Szemeredi to show that K_r-free, degree-d graphs have independent sets of size Omega_r(n log log d / d).

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

Nikhil Bansal: Approximating independent sets in sparse graphs. SODA 2015.
(referuje Martin Böhm)

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).

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

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

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

Deeparnab Chakrabarty, Sanjeev Khanna and Shi Li: On Restricted Assignment Makespan Minimization. SODA 2015. Also Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also

Gábor Braun, Sebastian Pokutta, Daniel Zink: Inapproximability of combinatorial problems via small LPs and SDPs. STOC 2015.

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]