# Seminář z aproximačních a online algoritmů

## Petr Kolman, Jiří Sgall

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

**11. 1. 2005 **(úterý [Tuesday], **15.00, MÚ Žitná 25**, **3.
patro**)

**Wojciech Jawor (UC Riverside, CA, USA): Competitive algortihms to
minimize flow time**

**Abstract: **
An area of scheduling that has received much attention lately is
job scheduling to minimize flow and stretch objectives. These
objective functions have many applications that include scheduling
jobs in operating systems, serving HTTP requests at web servers,
parallel computing and many others.

The talk will include a survey of the latest results on competitve
algorithms to minimize average and maximum flow. The discussion will
cover common variants of the problem: the preemptive and
nonpreemptive cases, resource augmentation models and others.

**4. 1. 2005 **(úterý [Tuesday], **15.00, MÚ Žitná 25**, **3.
patro**)

Daniel Král', Jiří Sgall, Tomáš Tichý: Randomized Strategies for the
Plurality Problem

(referuje Jiří Sgall)

**Abstract: **We study a game played by two players, Paul and
Carol.
At the beginning of the game, Carol fixes a coloring of $n$ balls. At
each turn, Paul chooses a pair of the balls and asks Carol whether the
balls have the same color. Carol truthfully answers his question.
Paul's goal is to determine the most frequent (plurality) color in the
coloring by asking as few questions as possible. The game is studied in
the probabilistic setting when Paul is allowed to flip a coin to choose
his next question. We find a strategy for Paul to determine the
plurality color with the expected number of $2n/3+O(\sqrt{n\log n})$
questions when the balls are colored by two colors, and we provide a
lower bound $2n/3-O(\sqrt{n})$ on the expected number of Paul's
questions in this case. In the general case when the balls are colored
by $k$ colors, we provide a lower bound $2kn/27-o(kn)$ on the expected
number of questions asked by Paul during the game.

**7. 12., 14. 12. 2004 **(úterý [Tuesday], **15.00, MÚ
Žitná 25**, **3. patro**)

Volkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized
pursuit-evasion with limited visibility (SODA 2004)

(referuje Petr Kučera)

**Abstract: **We study the following pursuit-evasion game: One or
more hunters are seeking to capture an evading rabbit on a graph. At
each round, the rabbit tries to gather information about the l ocation
of the hunters but it can see them only if they are located on adjacent
nodes. We show that two hunters suffice for catching rabbits with
limited visibility with high probability. We distinguish between
reactive rabbits who who move only when the hunter is visible and
general rabbits can employ more sophisticated strategies. We present
polynomial time algorithms that decide whether a graph G is hunter-win,
that is, if a single hunter can capture a rabbit of either kind on G.

**30. 11. 2004 **(úterý [Tuesday], **15.00, MÚ Žitná 25**, **3.
patro**
)

** **

Nikhil Bansal, Maxim Sviridenko:

**New approximability and inapproximability results for
2-dimensional Bin Packing**** **(SODA 2004)

(referuje Martin Pergel)

Abstract:
We study the 2-dimensional generalization of the classical Bin Packing
problem: Given a collection of rectangles of specified size (width,
height), the goal is to pack these into minimum number of square bins
of unit size. Currently, the best known approximation algorithm
achieves a guarantee of 1.69 in the asymptotic case (i.e. when the
optimum uses a large number of bins). However, an important open
question has been whether 2-dimensional bin packing is essentially
similar to the 1-dimensional case in that it admits an asymptotic
polynomial time approximation scheme (APTAS) or not? We answer the
question in the negative and show that the problem is APX hard in the
asymptotic case. On the other hand, we give an asymptotic PTAS for the
special case when all the rectangles to be packed are squares (or more
generally hypercubes). This improves upon the previous best known
guarantee of 1.454 for d = 2 and 2 - (2/3)d for d > 2, and settles
the approximability for this special case.

**16. 11., 23. 11. 2004 **(úterý [Tuesday], **15.00, MÚ Žitná 25**,
**3. patro**
)

**Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph
(Seffi) Naor: **

A General Approach to Online Network Optimization Problems (SODA
2004)

(referuje David Kronus)

Abstract: We study a wide range of online graph and network
optimization problems, focusing on problems that arise in the study of
connectivity and cuts in graphs. In a general online network design
problem, we have a communication network known to the algorithm in
advance. What is not known in advance are the bandwidth or cut demands
between nodes in the network. Our results include an O(log m log n)
competitive randomized algorithm for the online non-metric facility
location and for a generalization of the problem called the multicast
problem. In the non-metric facility location m is the number of
facilities and n is the number of clients. The competitive ratio is
nearly tight. We also present an O(log^2 n log k) competitive
randomized algorithm for the online group Steiner problem in trees and
an O(log^3 n log k) competitive randomized algorithm for the problem in
general graphs, where n is the number of vertices in the graph and k is
the number of groups. Finally, we design a deterministic O(log^3 n log
log n) competitive algorithm for the online multi-cut problem. Our
algorithms are based on a unified framework for designing online
algorithms for problems involving connectivity and cuts. We first
present a general O(log m)-deterministic algorithm for generating
fractional solution that satisfies the online connectivity or cut
demands, where m is the number of edges in the graph. This may be of
independent interest for solving fractional online bandwidth allocation
problems, and is applicable to the node version as well. The integral
solutions are obtained by an online rounding of the fractional
solution. This part of the framework is problem dependent, and applies
various tools including results on the approximate max-flow min-cut for
multicommodity the HST method and its extensions, certain rounding
techniques for dependent variables, and Re's new hierarchical
decomposition of graphs.

**2. 11., 9. 11. 2004 **(úterý [Tuesday], **15.00, MÚ Žitná
25**, **3. patro**
)

**Peter Sanders, Naveen Sivadasan, and Martin Skutella:**

Online Scheduling with Bounded Migration** **(ICALP 2004)

(referuje Tomáš Ebenlendr)

Abstract: Consider the classical online scheduling problem where
jobs that arrive one by one are assigned to identical parallel machines
with the
objective of minimizing the makespan. We generalize this problem by
allowing the current assignment to be changed whenever a new job
arrives, subject to the constraint that the total size of moved jobs is
bounded by \beta times
the size of the arriving job. Our main result is a linear time `online
approximation
scheme', that is, a family of online algorithms with compet itive
ratio
1+\epsilon and constant migration factor. This result is of particular
importance
if considered in the context of sensitivity analysis: While a newly
arriving
job may force a complete change of the entire structure of an optimal
schedule,
only very limited `local' changes suffice to preserve nearoptimal
solutions. We believe that this concept will find wide application in
its own right. We also present a simple deterministic online algorithms
with migration
factor 2.

**26. 10. 2004 **(úterý [Tuesday], **15.00, MÚ Žitná 25**, **3.
patro**)

**Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian,
Baruch
Schieber, and Maxim Sviridenko:**

**Further Improvements in Competitive Guarantees for QoS Buffering
**(ICALP 2004)

(referuje Tomáš Tichý)

Abstract: We study the behavior of algorithms for buffering
packets weighted
by different levels of Quality of Service (QoS) guarantees in a single
queue.
Buffer space is limited, and packet loss occurs when the buffer
overflows.
We describe a modification of the previously proposed preemptive greedy
algorithm
of for buffer management and give an analysis to show that this
algorithm
achieves a competitive ratio of at most 1.75. This improves upon recent
work
showing a 1.98 competitive ratio, and a previous result that shows a
simple
greedy algorithm has a competitive ratio of 2.

**19. 10. 2004 **(úterý [Tuesday], **15.00, MÚ Žitná 25**, **3.
patro**)

**J. Sgall: ****
Improved online algorithms for buffer management in QoS switches**

(spoluautoři M. Chrobak, W. Jawor, T. Tichy)

Abstrakt: V tomto článku studujeme problémy rozvrhování úloh s
jednotkovou
dobou trvání v reálném čase. Spíše než na technickou prezentaci
výsledků
se zaměřím na další související výsledky a modely a otevřené problémy.