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.