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

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

Sanjeev Arora,
Eden Chlamtac, Moses Charikar:
New
approximation guarantee for chromatic number.
STOC'06.

(referuje Jan Kadlec)

Abstract: We
describe how to color every 3-colorable graph with O(n^{0.2111})
colors, thus improving an algorithm of Blum and Karger from almost a
decade ago. Our analysis uses new geometric ideas inspired by the
recent work of Arora, Rao, and Vazirani on SPARSEST CUT, and these
ideas show promise of leading to further improvements.

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

Brian C. Dean, Michel X. Goemans,
Nicole Immorlica:

Finite
Termination of "Augmenting Path" Algorithms in the Presence of
Irrational Problem Data.
ESA'06.

(referuje Tomáš Ebenlendr)

**Abstract: **This paper considers two similar graph algorithms
that work by repeatedly increasing “flow” along “augmenting paths”: the
Ford-Fulkerson algorithm for the maximum flow problem and the
Gale-Shapley algorithm for the stable allocation problem (a
many-to-many generalization of the stable matching problem). Both
algorithms clearly terminate when given integral input data. For
real-valued input data, it was previously known that the Ford-Fulkerson
algorithm runs in polynomial time if augmenting paths are chosen via
breadth-first search, but that the algorithm might fail to terminate if
augmenting paths are chosen in an arbitrary fashion. However, the
performance of the Gale-Shapley algorithm on real-valued data was
unresolved. Our main result shows that, in contrast to the
Ford-Fulkerson algorithm, the Gale-Shapley algorithm always terminates
in finite time on real-valued data. Although the Gale-Shapley algorithm
may take exponential time in the worst case, it is a popular algorithm
in practice due to its simplicity and the fact that it often runs very
quickly (even in sublinear time) for many inputs encountered in
practice. We also study the Ford-Fulkerson algorithm when augmenting
paths are chosen via depth-first search, a common implementation in
practice. We prove that, like breadth-first search, depth-first search
also leads to finite termination (although not necessarily in
polynomial time).

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

Lisa Fleischer: Fast
Approximation Algorithms for Fractional Covering Problems with Box
Constraints. SODA'04.

(referuje Pavel Nejedlý)

**Abstract: **
We present the first combinatorial approximation scheme that yields a
pure approximation guarantee for linear programs that are either
covering problems with upper bounds on variables, or their duals.
Existing approximation schemes for mixed covering and packing problems
do not simultaneously satisfy packing and covering constraints exactly.
We present the first combinatorial approximation scheme that returns
solutions that simultaneously satisfy general positive covering
constraints and upper bounds on variable values. For input parameter
eps>0, the returned solution has positive linear objective function
value at most 1+eps times the optimal value. The general algorithm
requires O(eps^2 m log(c^T u)) iterations, where c is the objective
cost vector, u is the vector of upper bound values, and m is the number
of variables. Each iteration uses an oracle that. Finds an
(approximately) most violated constraint.

A natural set of problems that our work addresses are linear programs for various network design problems: generalized Steiner network, vertex connectivity, directed connectivity, capacitated network design, group Steiner forest. The integer versions of these problems are all NP-hard. For each of them, there is an approximation algorithm that rounds the solution to the corresponding linear program relaxation. If the LP solution is not feasible, then the corresponding integer solution will also not be feasible. Solving the linear program is often the computational bottleneck in these problems, and thus a fast approximation scheme for the LP relaxation means faster approximation algorithms.

21. 11., 28. 11. 2006 (úterý
[Tuesday], **9:00, MFF UK Malá
Strana S9**)

Jonathan A. Kelner, Daniel A.
Spielman: A
Randomized Polynomial-Time Simplex Algorithm for Linear Programming.
STOC'06.
předběžná verze ECCC
TR05-156

(referuje Marek Krčál)

7. 11., 14. 11. 2006 (úterý
[Tuesday], **9:00, MFF UK Malá
Strana S9**)

Jeff Edmonds and Kirk Pruhs: Balanced
Allocations of Cake.

(referuje Ondřej Zajíček)

24. 10., 31. 10. 2006 (úterý
[Tuesday], **9:00, MFF UK Malá
Strana S9**)

Henning Bruhn, Jakub Cerný,
Alexander Hall, Petr Kolman:

Single Source Multiroute
Flows and Cuts on Uniform Capacity Networks.
To appear in SODA'07.

(referuje Petr Kolman)

Abstract:
For an integer $h\geq 1$, an elementary
$h$-route flow is a flow
along $h$ edge disjoint paths between a source and a sink, each path
carrying a unit of flow, and a single commodity $h$-route flow is
a
non-negative linear combination of elementary $h$-route flows. An
instance
of a
single source multicommodity flow
problem for a graph $G=(V,E)$
consists of a source vertex $s\in V$ and $k$ sinks $t_1,...,t_k\in
V$;
we denote it $\CI=(s;t_1,...,t_k)$. In the single source
multicommodity multiroute flow problem, we are given an instance
$\CI=(s;t_1,...,t_k)$ and an integer $h\geq 1$, and the objective is
to
maximize the total amount of flow that is transferred from the source
to the
sinks so that the capacity constraints are obeyed and, moreover, the
flow of each commodity is an $h$-route flow.

We study the relation between classical and multiroute single source
flows
on networks with uniform capacities and we provide a tight bound. In
particular, we prove the following result. Given an instance
$\CI=(s;t_1,...,t_k)$ such that each $s-t_i$ pair is $h$-connected,
the
maximum classical flow between $s$ and the $t_i$'s is at most
$2(1-1/h)$-times larger than the maximum $h$-route flow between $s$ and
the $t_i$'s and this is the best possible bound for $h\geq 2$. This, as
we
show, is in contrast to the situation of general multicommodity
multiroute
flows that are up to $k(1-1/h)$-times smaller than their classical
counterparts.

As a corollary, we establish a max-flow min-cut theorem for the single
source multicommodity multiroute flow and cut. An $h$-disconnecting
cut for $\CI$ is a set of edges $F\subseteq E$ such that for
each $i$,
the
maximum $h$-route flow between $s-t_i$ is zero.
We show that the maximum $h$-route flow is within $2(h-1)$ of the
mininimum
$h$-disconnecting cut, independently of the number of commodities; we
also
describe a $2(h-1)$-approximation algorithm for the minimum
$h$-disconnecting cut problem.

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

M. Chrobak, W. Jawor, J. Sgall, T.
Tichy:

**Online
scheduling of equal-length jobs:
Randomization and restarts help**. To appear in SIAM J.
Comput.

(referuje Jiří Sgall)

Abstract: We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below $2$ and show several lower bounds on the competitive ratios. First, we give a barely random $5/3$-competitive algorithm that uses only one random bit. Second, we give a deterministic $3/2$-competitive algorithm in the model that allows restarts.