# Semináø z aproximaèních a online algoritmù

## Petr Kolman, Jiøí Sgall

### 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 Deadline­TSP 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 Deadline­TSP 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 Deadline­TSP, and extend this algorithm to an O(log^2 n) approximation for the Time­Window 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 corre­lated) in games with a large number of players; such games, in order to be computationally meaningful, must be presented in some succinct, game­specific way. We develop a general framework for obtain­ing polynomial­time 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 polynomial­time 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 non­empty 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 Semi­Greedy, 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