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