**18. 5. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, and Haifeng
Xu: ****Caching
is Hard - Even in the Fault Model. **ESA 2010.

(referuje Peter Šufliarsky)

**Abstract: **We prove strong NP-completeness for the four
variants of caching with multi-size pages. These four variants are
obtained by choosing either the fault cost or the bit cost model, and
by combining it with either a forced or an optional caching policy.
This resolves two complexity questions in the area of paging and
caching that were open since the 1990s.

**4. 5., 11. 5. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis
Gharan, and Amin Saberi:
An
O(log
n/
log
log
n)-approximation
Algorithm
for the Asymmetric
Traveling Salesman Problem. **SODA 2010.

(referuje Vítězslav Zajíc)

**Abstract:** We consider the Asymmetric Traveling Salesman
problem for costs satisfying the triangle inequality. We derive a
randomized algorithm which delivers a solution within a factor O(log n/
log log n) of the optimum with high probability.

**20. 4., 27. 4. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Ron Aharoni, Eli Berger: The
intersection
of
a
matroid
and
a simplicial complex.** Trans. AMS**
358 **(2006), 4895-4917.

(referuje Marek Krčál)

**Abstract:** A classical theorem of Edmonds provides a min-max
formula relating the
maximal size of a set in the intersection of two matroids to a
"covering" parameter. We generalize this theorem, replacing one of the
matroids by a general simplicial complex. One application is a solution
of the caser=3
of a matroidal version of Ryser's conjecture. Another is an upper bound
on the minimal number of sets belonging to the intersection of two
matroids, needed to cover their common ground set. This, in turn, is
used to derive a weakened version of a conjecture of Rota. Bounds are
also found on the dual parameter--the maximal number of disjoint sets,
all spanning in each of two given matroids. We study in detail the case
in which the complex is the complex of independent sets of a graph, and
prove generalizations of known results on ``independent systems of
representatives" (which are the special case in which the matroid is a
partition matroid). In particular, we define a notion of k-matroidal
colorability of a graph, and prove a fractional version of a
conjecture, that every graph G is
2-Delta(G) matroidally colorable.

**6. 4., 13. 4. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Chandra Chekuri,
Alina Ene,
Nitish Korula:
Unsplittable
Flow
in
Paths
and
Trees
and
Column-Restricted
Packing
Integer Programs. **
APPROX-RANDOM 2009.

(referuje Dušan Knop)

**16. 3., 23. 3. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

** Siddharth Barman and Shuchi Chawla: Region Growing for Multi-Route Cuts. **SODA
2010.

(referuje Petr Kolman)

**9. 3. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**René Sitters: Efficient
algorithms
for
average
completion
time
scheduling.
**(referuje Ondřej Zajíček)

**2. 3. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

Na úvodním semináři povím něco o výsledcích, které jsme získali během prosincové návštěvy Lukasze Jeze. Jde o nový algoritmus a nový dolní odhad, oboje pro bipartitní grafy, a oboje zlepšuje dosavadní známé odhady pro asymptotický kompetitivní poměr.