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]

10. 5. 2016 (úterý [Tuesday], 14:00, MFF UK Malá Strana S7)

F. Bruce Shepherd, Adrian Vetta: The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems.
(referuje Petr Kolman)

Abstract: We consider single-sink network flow problems. An instance consists of a capacitated graph (directed or undirected), a sink node t and a set of demands that we want to send to the sink. Here demand i is located at a node s_i and requests an amount d_i of flow capacity in order to route successfully. Two standard objectives are to maximise (i) the number of demands (cardinality) and (ii) the total demand (throughput) that can be routed subject to the capacity constraints. Furthermore, we examine these maximisation problems for three specialised types of network flow: unsplittable, confluent and priority flows.
In the unsplittable flow problem (UFP), we have edge capacities, and the demand for s_i must be routed on a single path. In the  confluent flow problem, we have node capacities, and the final flow must induce a tree. Both of these problems have been studied extensively, primarily in the single-sink setting. However, most of this work imposed the {\em no-bottleneck assumption} (that the maximum demand d_max is at most the minimum capacity u_min). Given the no-bottleneck assumption (NBA), there is a factor 4.43-approximation algorithm due to Dinitz et al. for the unsplittable flow problem. Under the stronger assumption of uniform capacities, there is a factor 3-approximation algorithm due to Chen et al. for the confluent flow problem. However, unlike the UFP, we show that a constant factor approximation algorithm cannot be obtained for the single-sink confluent flows even with the NBA.
Without NBA, we show that maximum cardinality single-sink UFP is hard to approximate to within a factor n^(0.5-\eps) even when all demands lie in a small interval [1,1+delta] where delta>0 (but has polynomial input size). This is very sharp since when delta=0, this becomes a maximum flow problem.

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]