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

Petr Kolman, Jiří Sgall

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

UMLUVENO: v LS 2016 se seminář koná v úterý od 14:00 v posluchárně S7.

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]

19. 4. 2016 (Úterý [Tuesday], 14:00, MFF UK Malá Strana S7)

Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. SODA 2016.
(referuje Pavel Veselý)

Abstract: In the strip packing problem we are given a set of rectangular items that we want to place in a strip of given width such that we minimize the height of the obtained packing. It is a very classical two-dimensional packing problem that has received a lot of attention and it has applications in many settings such as stock-cutting and scheduling. A straight-forward reduction from Partition shows that the problem cannot be approximated with a better absolute factor than 3/2. However, this reduction requires the numeric values to be exponentially large. In this paper, we present a (1.4 + ε)-approximation algorithm with pseudo-polynomial running time. This implies that for polynomially bounded input data the problem can be approximated with a strictly better ratio than for exponential input which is a very rare phenomenon in combinatorial optimization.

Our algorithm is based on a structural lemma proving that there is a packing of height (1.4 + ε)OPT that allows a partition of the packing area into few rectangular boxes. These boxes have the property that they decouple the packing decisions for the items that are thin and high, wide and narrow, or large in both dimensions. The interaction of these item types is typically a major problem when designing algorithms and our partition completely solves this. Particularly difficult are items that are thin and high since a single one of them can increase the optimal packing height significantly if placed wrongly and there can be up to Ω(n) of them. For those items the box partition is even fine grained enough so that all items in a box have essentially the same height. This reduces the usually difficult packing decisions for these items to a problem that can be solved easily via a pseudo-polynomial time dynamic program.

The mentioned reduction from Partition also breaks down if we allow to drop a constant number of input items (while the compared optimal solution cannot do this). We show that then we can approximate the problem much better and present a polynomial time algorithm computing a packing of height at most (1 + ε)OPT that needs to drop at most Oε(1) items.

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

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

Nikhil Bansal, Aravind Srinivasan, and Ola Svensson: Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines. STOC 2016, also

Haris Aziz, and Simon Mackenzie: A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents. STOC 2016, also

Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese: New Approximation Schemes for Unsplittable Flow on a Path. SODA 2015.

B. Shepherd, A. Vetta, G.T. Wilfong: Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. FOCS 2015

B. Shepherd, A. Vetta: Inapproximability of Single-Sink Unsplittable and Confluent Flows. 2015.

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(m^2 log m)-Competitive Algorithm for Online Machine Minimization. SODA 2016. Also

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

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]

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

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

Lorenzo Orecchia, Zeyuan Allen Zhu: Flow-Based Algorithms for Local Graph Clustering. SODA 2014. Also

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