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 near­optimal 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.