**21. 12. 2010****, 11. 1. 2011** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

**Jiří Sgall: Bounded space bin packing.**

(joint work with Marek Chrobak and Gerhard Woeginger)

**14. 12. 2010, 4. 1. 2011** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

**Nikhil Bansal and Kirk Pruhs: The Geometry of
Scheduling. **FOCS 2010.

(referuje Tomáš Ebenlendr)

**Abstract:** We consider the following general scheduling
problem: The input consists of n
jobs, each with an arbitrary release time, size, and a monotone
function
specifying the cost incurred when the job is completed at a particular
time.
The objective is to find a preemptive schedule of minimum aggregate
cost. This
problem formulation is general enough to include many natural
scheduling
objectives, such as weighted flow, weighted tardiness, and sum of flow
squared.
Our main result is a randomized polynomial-time algorithm with an
approximation
ratio O(log log nP), where P is the maximum job size. We also give an
O(1)
approximation in the special case when all jobs have identical release
times.
The main idea is to reduce this scheduling problem to a particular
geometric
set-cover problem which is then solved using the local ratio technique
and
Varadarajan's quasi-uniform sampling technique. This general
algorithmic
approach improves the best known approximation ratios by at least an
exponential factor (and much more in some cases) for essentially all of
the
nontrivial common special cases of this problem. Our geometric
interpretation
of scheduling may be of independent interest.

**30. 11., 7. 12. 2010** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

**Bjarni Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and
Mario Szegedy: Streaming
algorithms for independent sets.** ICALP 2010.

(referuje Michal Dzetkulič)

**16. 11., 23. 11., 30. 11. 2010** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

**M. Hajiaghayi, R. Khandekar, G. Kortsarz, and J. Mestre: The
checkpoint problem.** APPROX 2010.

(referuje Dušan Knop)

**Abstract. **In this paper we consider the sum checkpoint (SCP)
and the maximum checkpoint (MCP) problem. These problem have several
natural applications, e.g., in urban transportation and network
security. In a sense, they combine the multicut problem and the minimum
membership set cover problem. For the sum objective we show that
weighted SCP is equivalent, with respect to approximability, to
undirected multicut. Thus there exists an O(log n) approximation for
SCP in general graphs. Our current approximability results for the max
objective have a wide gap: we provide an approximation factor of
O(sqrt(n log n/opt)) for MCP and a hardness of 2 under the assumption
P!=NP. The hardness holds for trees, in which case we can obtain an
asymptotic approximation factor of 2. Finally we show strong hardness
for the well-known problem of finding a path with minimum forbidden
pairs, which in a sense can be considered the dual to the checkpoint
problem. Despite various works on this problem, hardness of
approximation was not known prior to this work. We show that the
problem cannot be approximated within c n for some constant c > 0,
unless P = NP. This is the strongest type of hardness possible. It
carries over to directed acyclic graphs and is a huge improvement over
the plain NP-hardness of Gabow (SIAM J. Comp 2007, pages 1648–1671).

**9. 11., 16. 11. 2010** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

(referuje Ondřej Zajíček)

**26. 10., 2. 11. 2010** (úterý [Tuesday], **12:20,
MFF UK Malá
Strana, S7**)

**Klaus Jansen: Approximate
Strong
Separation
with Application in Fractional Graph Coloring and
Preemptive Scheduling. **STACS 2002.

(referuje Marek Krčál)

**Abstract:** In this paper we show that approximation algorithms
for the weighted
independent set and s-dimensional knapsack problem with ratio α can be
turned into approximation algorithms with the same ratio for fractional
weighted graph coloring and preemptive resource constrained scheduling.
In order to obtain these results, we generalize known results by
Grötschel, Lovasz and Schrijver on separation, non-emptiness test,
optimization and violation in the direction of approximability.

**Petr Kolman: Towards Duality of Multicommodity Multiroute Cuts
and Flows: Multilevel Ball-Growing
**(joint work with Christian Scheideler)