## Předchozí program semináře, letní semestr 2005 [Previous program, Spring 2005]

**19. 5. 2005 **(čtvrtek
[Thursday], **9.00, MFF UK Malá
Strana S7**)

Graham Cormode, S. Muthukrishnan: The
String Edit Distance Matching Problem with Moves.** **SODA,
2002.

(referuje Tomáš Vyskočil)

**12. 5. 2005 **(čtvrtek
[Thursday], **9.00, MFF UK Malá
Strana S7**)

Henning Bruhn, Petr Kolman: Single Source Multiroute Flows and
Cuts on Uniform Capacity Networks

(referuje Petr Kolman)

**Abstract:**
An instance of *the single source
flow problem* for a graph $G=(V,E)$
consists of a source vertex $s\in V$ and $k$ sinks $t_1,\ldots, t_k\in
V$;
we denote it $\CI=(s;t_1,\ldots,t_k)$. In the single source
multicommodity
{\em multiroute} flow problem, we are given an instance
$\CI=(s;t_1,\ldots,t_k)$ 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 (an $h$-route flow is a non-negative linear
combination of
elementary $h$-flows where an elementary $h$-flow is a flow along $h$
edge
disjoint paths between the source and the sink, each path carrying a
unit of
flow). An {\em $h$-disconnecting cut} for $\CI$ is a set of edges
$F\subseteq E$ such that no $s-t_i$ pair is $h$-connected in $(V,E-F)$.

We establish a max-flow min-cut theorem for the single source
multiroute
flow and the minimum disconnecting cut on networks with uniform
capacities.
In particular, we show that the max-flow is within $2h-2$ of the
min-cut,
independently of the number of commodities; we also describe a
$2(h-1)$-approximation algorithm for the minimum $h$-disconnecting cut
problem. The theorem follows from another result that is of its own
interest. Given an instance $\CI=(s;t_1,\ldots,t_k)$ such that each
$s-t_i$
pair is $h$-connected, the maximum classical flow between $s$ and
$t_i$'s is
at most $2(1-1/h)$-times larger than the maximum multiroute flow
between $s$
and $t_i$'s and this is the best possible bound. This is in contrast
with
the situation of general multicommodity multiroute flows where the
ratio
depends linearly on the number of commodities even for $h=2$.

**28. 4., 26. 5. 2005 **(čtvrtek [Thursday], **9.00, MFF UK
Malá
Strana S7**)

**Nikhil Bansal, Avrim Blum, Shuchi
Chawla, Adam Meyerson: Approximation Algorithms for DeadlineTSP and
Vehicle Routing with
Time-Windows.** STOC, 2004.

(referuje Martin Pergel)

**Abstract:** Given a metric space G on n nodes, with a start
node r
and deadlines D(v) for each vertex v, we consider the DeadlineTSP
problem of finding a path starting at r that visits as many nodes as
possible by their deadlines. We also consider the more general Vehicle
Routing with Time Windows problem, in which each node v also has a
release time R(v) and the goal is to visit as many nodes as possi ble
within their ``time-windows'' [R(v), D(v)]. No good approximations
were known previously for these problems on general metric spaces. We
give an O(log n) approximation algorithm for DeadlineTSP, and extend
this algorithm to an O(log^2 n) approximation for the TimeWindow
problem. We also give a bicriteria approximation algorithm for both
problems: Given an eps>0, our algorithm produces a log(1/eps)
approximation, while exceeding the deadlines by a factor of 1+eps. We
use as a subroutine for these results a constant factor approximation
that we develop for a generalization of the orienteering problem in
which both the start and the end nodes of the path are fixed. In the
process, we give a 3-approximation to the orienteering problem,
improving on the previously best known 4-approximation.

**21. 4. 2005 **(čtvrtek [Thursday], **9.00, MFF UK Malá
Strana S7**)

**Avrim Blum, Jason D. Hartline:
Near-Optimal
Online Auctions.**
SODA, 2005.

(referuje Ondřej Zajíček)

**Abstract:** We consider the online auction problem proposed by
Bar-Yossef, Hildrum, and Wu [4] in which an auctioneer is selling
identical items to bidders arriving one at a time. We give an auction
that achieves a constant factor of the optimal profit less an O(h)
additive loss term, where h is the value of the highest bid.
Furthermore, this auction does not require foreknowledge of the range
of bidders’ valuations. On both counts, this answers open questions
from [4, 5]. We further improve on the results from [5] for the online
posted-price problem by reducing their additive loss term from O(h log
h log log h) to O(h log log h). Finally, we define the notion of an
(offline) attribute auction for modeling the problem of auctioning
items to consumers who are not a-priori indistinguishable. We apply our
online auction solution to achieve good bounds for the attribute
auction problem with 1-dimensional attributes.

**7. 4., 14. 4. 2005 **(čtvrtek [Thursday], **9.00, MFF UK
Malá
Strana S7**)

**Christos H. Papadimitriou and Tim
Roughgarden:
Computing Equilibria in Multi-Player Games.
**SODA, 2005.

(referuje Petr Kučera)

**Abstract:** We initiate the systematic study of algorithmic
issues
involved in finding equilibria (Nash and correlated) in games with a
large number of players; such games, in order to be computationally
meaningful, must be presented in some succinct, gamespecific way. We
develop a general framework for obtaining polynomialtime algorithms
for optimizing over correlated equilibria in such settings, and show
how it can be applied successfully to symmetric games (for which we
actually find an exact polytopal characterization), graphical games,
and congestion games, among others. We also present complexity results
implying that such algorithms are not possible in certain other such
games. Finally, we present a polynomialtime algorithm, based on
quantifier elimination, for finding a Nash equilibrium in symmetric
games when the number of strategies is relatively small.

**24. 3., 31. 3. 2005 **(čtvrtek [Thursday], **9.00, MFF UK
Malá Strana S7**)

**Nikhil Bansal, Tracy Kimbrel, and Maxim Sviridenko: Job Shop
Scheduling with Unit Processing Times.** SODA 2005

(referuje Tomáš Ebenlendr)

**Abstract:** We consider randomized algorithms for the
preemptive
job shop problem, or equivalently, the case in which all operations
have unit length. We give an 1.45-approximation for the case of two
machines, an improved approximation ratio of O( log m / log log m )
for an arbitrary number m of machines, and the first
(2+eps)-approximation for a constant number of machines. The first
result is via an approximation algorithm for a string matching problem
which is of independent interest.

**17. 3. 2005 **(čtvrtek [Thursday], **9.00, MFF UK Malá
Strana S7**)

**Susanne Albers, Markus Schmidt: On the Performance of
Greedy Algorithms in Packet Buffering**. STOC'04

(referuje Tomáš Tichý)

**Abstract:** We study a basic buffer management problem that
arises
in network switches. Consider m input ports, each of which is equipped
with a buffer (queue) of limited capacity. Data packets arrive online
and can be stored in the buffers if space permits; otherwise packet
loss occurs. In each time step the switch can transmit one packet from
one of the buffers to the output port. The goal is to maximize the
number of transmitted packets. Simple arguments show that any
reasonable algorithm, which serves any nonempty buffer, is
2-competitive. We prove that greedy algorithms are not better than
2-competitive no matter how ties are broken. In the second part of the
paper we present the first deterministic online algorithm that is
better than 2-competitive. We develop a modified greedy algorithm,
called SemiGreedy, and prove that it achieves a competitive ratio of
17/9=1.89. The new algorithm is simple, fast and uses little extra
memory. Only when the risk of packet loss is low, it does not serve the
longest queue. Additionally we study scenarios when an online algorithm
is granted additional resources. We consider resource augmentation with
respect to memory and speed, i.e. an online algorithm may be given
larger buffers or higher transmission rates. We analyze greedy and
other online strategies.

**10. 3. 2005 **(čtvrtek [Thursday], **9.00, MFF UK Malá
Strana S7**)

**E. Koutsoupias, C. H. Papadimitriou Worst-case
equilibria, STACS
99.
G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination
mechanisms, ICALP 2004.**

(referuje J. Sgall)

**Abstrakt: **V poslední době se stále častěji klasické
optimalizační problémy studují v situaci, kdy optimalizaci provádí
distibuovaně několik "agentů", kteří nemají za cíl dosáhnout
globálního optima, ale maximalizovat svůj "sobecký" zisk. Podle
uvedených dvou článků vysvětlíme základní pojmy z této oblasti.

**3. 3. 2005 **(čtvrtek [Thursday], **9.00, MFF UK Malá
Strana S7**)

Petr Kolman: Minimum Common String Partition Problem: Hardness
and Approximations

**Abstract: **String comparison is a fundamental problem
in
computer science, with applications in areas such as computational
biology, text processing or compression. In this talk we address
the minimum common string partition problem, a string comparison
problem with tight connection to the problem of sorting by reversals
with duplicates, a key problem in genome rearrangement. We will deal
with hardness of the problem, hardness of its approximation, and we
will also present approximation algorithms.

A {\em partition} of a string $A$ is a sequence $\calP =
(P_1,P_2,\dots,P_m)$ of strings, called the \emph{blocks}, whose
concatenation is equal to $A$. Given a partition $\calP$ of a string
$A$ and a partition $\calQ$ of a
string $B$, we say that the pair $\angled{\calP,\calQ}$ is a {\em
common partition} of $A$ and $B$ if $\calQ$ is a permutation of
$\calP$. The {\em minimum common string partition} problem
({\MCSP}) is to find a common partition of two strings $A$ and $B$ with
the minimum number of blocks. The restricted version of {\MCSP}
where each letter occurs at most $k$ times in each input string, is
denoted by $k$-{\MCSP}.

Marek Chrobak, Petr Kolman, Jiri Sgall: The Greedy Algorithm
for the
Minimum Common String Partition Problem. APPROX-RANDOM 2004:84-95

Avraham Goldstein, Petr Kolman, Jie Zheng: Minimum
Common String
Partition Problem: Hardness and Approximations. ISAAC 2004: 484-495