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 http://list.math.cas.cz/listinfo/algo-seminar.

Kontakt

http://kam.mff.cuni.cz/~kolman/, tel. 221 914 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 221 914 293.

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

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

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

Abstract: We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Pradel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.


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

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

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

Martin Aumuller and Martin Dietzfelbinger:  Optimal Partitioning for Dual Pivot Quicksort. ICALP 2013. Also http://arxiv.org/abs/1303.5217 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]