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