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

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]

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

Marcin Bienkowski: An Optimal Lower Bound for Buffer Management in Multi-Queue Switches. Algorithmica 68:426-447, 2012. Preliminary version SODA 2011.

Abstract: In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput.

We present a tight lower bound of e/(e−1)≈1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.


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

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

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

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also http://arxiv.org/abs/1409.0607.

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 http://arxiv.org/abs/1410.7506.Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also http://arxiv.org/abs/1412.7693.

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

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.

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]