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

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: čtvrtek od 14:00, posluchárna S8 - první seminář 27. 2.

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]

10. 4. 2014 (čtvtek [Thursday], 14:00, MFF UK Malá Strana S8)

Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh: Faster Parameterized Algorithms using Linear Programming. arXiv:1203.0833

Abstract: We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O((2.618)k) algorithm for the problem. Here k is the excess of the vertex cover size over the LP optimum, and we write O(f(k)) for a time complexity of the form O(f(k)nO(1)), where f(k) grows exponentially with k. We proceed to show that a more sophisticated branching algorithm achieves a runtime of O(2.3146k).
Following this, using known and new reductions, we give O(2.3146k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an O(1.5214k) algorithm for Ko\"nig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The most notable improvement is the new bound for Odd Cycle Transversal - this is the first algorithm which beats the dependence on k of the seminal O(3k) algorithm of Reed, Smith and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of Vertex Cover with at most 2kclogk vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

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

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

Nikhil Bansal and Arindam Khan: Improved Approximation Algorithm for Two-Dimensional Bin Packing. SODA 2014.
(referuje Jan Voborník)

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

Reuven Bar-Yehuda, Dror Rawitz: On the Equivalence Between the Primal-Dual Schema and the Local Ratio Technique. SIAM J. Discrete Math., 19(3), 762–797.

Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick: Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. SODA 2014.

Stavros G. Kolliopoulos, Yannis Moysoglou: The 2-valued case of makespan minimization with assignment constraints. Inf. Process. Lett. 113(1-2): 39-43 (2013)

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.

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]

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]