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

Petr Kolman, Jiří Sgall

Předchozí program semináře, zimní semestr 2012 [Previous program, Fall 2012]

8. 1. 2013 (úterý [Tuesday], 10:40, MFF UK Malá Strana, chodba IÚUK/KAM 3. patro)

James M. Davis and David P. Williamson: A Dual-Fitting 3/2-Approximation Algorithm for Some Minimum-Cost Graph Problems. ESA 2012.
v kombinaci s Basile Couëtoux: A 3/2 approximation for a constrained forest problem. ESA 2012.
(referuje Ondřej Bílka)

Abstract: In an ESA 2011 paper, Couetoux [2] gives a beautiful 3/2 2-approximation algorithm for the problem of nding a minimum-cost set of edges such that each connected component has at least k vertices in it. The algorithm improved on previous 2-approximation algorithms for the problem. In this paper, we reanalyze Couetoux's algorithm using dual-fitting and show how to generalize the algorithm to a broader class of graph problems previously considered in the literature.

11. 12., 18. 12. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, chodba IÚUK/KAM 3. patro)

Thomas Rothvoss: The Entropy Rounding Method in Approximation Algorithms. SODA 2012.
(referuje Lukáš Mach)

Abstract: Let A be a matrix, c be any linear objective function and x be a fractional vector, say an LP solution to some discrete optimization problem. Then a recurring task in theoretical computer science (and in approximation algorithms in particular) is to obtain an integral vector y such that Ax is roughly Ay and c*y exceeds c*x by only a moderate factor.
We give a new randomized rounding procedure for this task, provided that A has bounded Delta-approximate entropy. This property means that for uniformly chosen random signs chi(j) in {-1,+1} on any subset of the columns, the outcome A*chi can be approximately described using a sub-linear number of bits in expectation.
To achieve this result, we modify well-known techniques from the field of discrepancy theory, especially we rely on Beck's entropy method, which to the best of our knowledge has never been used before in the context of approximation algorithms. Our result can be made constructive using the Bansal framework based on semidefinite programming.
We demonstrate the versatility of our procedure by rounding fractional solutions to column-based linear programs for some generalizations of Bin Packing. For example we obtain a polynomial time OPT + O(log^2 OPT) approximation for Bin Packing With Rejection and the first AFPTAS for the Train Delivery problem.

27. 11., 4. 12. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, chodba IÚUK/KAM 3. patro)

Andras Sebo, Jens Vygen: Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraph. ArXiv:1201.1870.
(referuje Martin Koutecký) 

Abstract: We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.

20. 11. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, chodba IÚUK/KAM 3. patro)

Nikhil Devanur, Kamal Jain and Robert Kleinberg: Randomized Primal-Dual analysis of RANKING for Online Bi-Partite Matching. SODA 2013.
(referuje Martin Böhm)

Abstract: We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani [KVV90] is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. [AGKM11]. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgetedallocation problem with small bids (also called the AdWords problem) of Mehta et al. [MSVV05].

6. 11., 13. 11. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, pracovna 326)

Andrew Mcgregor and Paul Valiant. The Shifting Sands Algorithm. SODA 2012.
(referuje Tomáš Masařík)

Abstract: We resolve the problem of small-space approximate selection in random-order streams. Specifically, we present an algorithm that reads the n elements of a set in random order and returns an element whose rank differs from the true median by at most n^{1/3+o(1)} while storing a constant number of elements and counters at any one time. This is optimal: it was previously shown that achieving better accuracy required poly(n) memory. However, it was conjectured that the lower bound was not tight and that a previous algorithm achieving an n^{1/2+o(1)} approximation was optimal. We therefore consider the new result a surprising resolution to a naturaland basic question.

23. 10., 30. 10. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, pracovna 326)

Martin Groß, Martin Skutella: Maximum Multicommodity Flows over Time without Intermediate Storage. ESA 2012.
(referuje Dušan Knop)

Abstract: Flows over time generalize classical ``static'' network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.\,g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known $(2+\varepsilon)$-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO~2002).

9. 10., 16. 10. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, pracovna 326)

Gy. Dósa and J. Sgall: First Fit and Best Fit bin packing: A new analysis

Abstract: In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. First Fit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. Best Fit algorithm packs each item into the most full bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of First Fit and Best Fit bin packing algorithm is equal to 1.7. We give a new and simple analysis that proves the same asymptotic ratio. Furthemore, building on this method, we prove that also the {\em absolute} approximation ratio for First Fit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, First Fit always uses at most $\lfloor1.7\cdot\OPT\rfloor$ bins. We also show {\em matching lower bounds} for a majority of values of OPT, i.e., we give instances on which First Fit uses exactly $\lfloor1.7\cdot\OPT\rfloor$ bins. Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of First Fit was $12/7\approx 1.7143$. Recently a bound of $101/59\approx 1.7119$ was claimed.