Algorithmen, Struktur, Zufall - Hauptseite Algorithmen, Struktur, Zufall

Learn- & Workshop 2003

"Zufall in Erstellung und Analyse von Algorithmen"

Vortragende: Dimitris Achlioptas, Yossi Azar

Dimitris AchlioptasDimitris Achlioptas
Yossi AzarYossi Azar

Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), 18.-20. Oktober 2003

Zeitplan:


Samstag, 18. Oktober 2003
8:30 Begrüßung & Einleitung
9:00 Dimitris Achlioptas Teil I
10:00 Kaffeepause
10:30 Dimitris Achlioptas
Dimitris AchlioptasDimitris Achlioptas
Fortsetzung
11:30 Mittagessen
13:30 Anusch Taraz Colouring various random graphs in polynomial expected running time
14:00 Kaffeepause
14:30 Yossi Azar Teil I
15:30 Kaffeepause
16:00 Yossi Azar Fortsetzung

Sonntag, 19. Oktober 2003
9:00 Yossi Azar Teil II
10:00 Kaffeepause
10:30 Yossi Azar
Yossi AzarYossi Azar
Fortsetzung
11:30 Mittagessen
13:30 Tjark Vredeveld Smoothed competitive analysis: lower bounds for non-clairvoyant scheduling
14:00 Kaffeepause
14:30 Dimitris Achlioptas Teil II
15:30 Kaffeepause
16:00 Dimitris Achlioptas Fortsetzung
20:00 Konzert des Berliner Philharmonie Orchesters im Kammermusiksaal, Philharmonie

Montag, 20. Oktober 2003
9:00 Dimitris Achlioptas Teil III
10:00 Kaffeepause
10:30 Dimitris Achlioptas
das Publikum zeigte sich zufriedendas Publikum zeigte sich zufrieden
Fortsetzung
11:45 Mittagessen
13:30 Thomas Voigt Edge-Expansion of Abstract Cubical Complexes
14:00 Kaffeepause
14:30 Yossi Azar Teil III
15:30 Kaffeepause
16:00 Yossi Azar Fortsetzung
17:00 Abschluss

Zusammenfassungen

Dimitris Achlioptas

The three talks will cover the following material.

  1. Algorithmic Applications of Random Matrices

    1. Imagine that we want to compute the "top few" eigenvalues of a matrix A. We will prove that either this is not worth doing, or that we can begin by randomly throwing away the vast majority of entries of A.
    2. Consider any set of n points in d-dimensional Euclidean space, represented as an n x d matrix A. Multiply A with a d x k matrix B where each entry of B is independently set to ± 1 with equal probability. We prove that if k=Theta(log n) then the k-dimensional pointset corresponding to AB is an embedding of the original pointset into k-dimensional Euclidean space such that all "m choose 2" distances are preserved within a (1+epsilon) factor with high probability.

  2. Approximation Markov chains by Differential Equations

    It is often possible to model the execution of an algorithm on a random structure by a finite number of parameters P = (p_1,p_2,...,p_k) where the evolution of P forms a Markov chain. In such cases (and with few very reasonable additional conditions), a powerful theorem of Wormald allows one to write a system of differential equations such that provably, with high probability the (random) evolution of P is very close to the (deterministic) solution of the equations.
    We will use this theorem to prove that almost all graphs with average degree 4 are 3-colorable (including 4-regular graphs).

  3. A new look at the Second Moment Method

    For any non-negative random variable X, the probability that X is strictly positive is at least E[X]^2 / E[X2]. This is known as "The Second Moment Method" and has been a mainstay of probabilistic combinatorics since the field's infancy. Recently (and rather unexpectedly) the second moment method has been successfully applied to Random [MAX] k-SAT, Random Hypergraph Colorability and Random Graph Coloring, essentially, by letting X be the number of solutions to each problem. We will see what "essentially" means for each problem and, if time allows, prove the following:
    With probability that tends to 1 as n tends to infinity, the chromatic number of a random graph G(n,p=d/n) is either k or k+1, where k is the smallest integer such that d < 2k logk.

Yossi Azar

I will discuss the power of randomization in online algorithms both for minimizing cost and maximizing the benefit problems. First I will talk about models of balls in boxes and show that having two random choices can decrease considerably the maximum number of balls in a box compared with having only one random choice. Second, I will discuss the benefit version and show that one can choose a box at random and get there a large number of balls even if the balls are placed in the boxes by an adversary. Next, I will show how fractional online algorithms can be transformed into online randomized ones and how online randomized algorithms can be derandomized in an online fashion for the set cover problem. At last I will talk about deterministic admission control algorithms and how to use them to get randomized algorithms for the maximum edge disjoint path problem.

  1. Balanced Allocation (The Power of Two Random Choices)

    Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1))ln n / ln ln n balls in it. Suppose instead, that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n / ln 2 + O(1) balls -- exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.

  2. Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time

    Suppose an adversary sequentially places balls into n boxes. We are allowed to choose one of these boxes at a time that we select (not necessarily at the beginning) and our benefit would be the number of balls that the adversary would place in the chosen box after the selection time. Somewhat surprisingly, we show that one can get poly-logarithmic fraction of the number of balls in the fullest box with probability 1-ε.
    We extend this problem to a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the decision-maker is to select the option that will have the best future performance. This task is made difficult by the constraint that the decision-maker has no way to predict the future performance of any of the options. We find that the decision-maker can still (at least in several important scenarios) pick a winner with high probability.

  3. The Online Set Cover Problem

    Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm one-by-one. Once a new element is given, the algorithm has to cover it by some set containing it (if it has not been already covered earlier). We assume that the possible n elements and m sets are known in advance to the algorithm, however, the subset of the elements given by the adversary is not known in advance to the algorithm. The objective is to minimize the total cost of the sets chosen by the algorithm.
    We present an O(log m log n) competitive deterministic algorithm for the problem, and establish a nearly matching lower bound for all interesting values of m and n. The techniques used are based on converting fractional solutions into integer ones using randomization and by de-randomization of an on-line algorithms.

  4. Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms

    We consider the maximum disjoint paths problem in the on-line setting. We are given a sequence of connection requests for some communication network. Each request consists of a pair of nodes, that wish to communicate over a path in the network. The request has to be immediately connected or rejected, and the goal is to maximize the number of connected pairs, such that no two paths share an edge.
    We present constant-competitive algorithm for the problem on the line. The algorithm is randomized and preemptive. Our result should be contrasted with the Ω(log n) lower bounds for deterministic preemptive algorithms of Garay et al. and the Ω(log n) lower bounds for randomized non-preemptive algorithms of Lipton and Tomkins and Awerbuch et al. The result is also generalized to the call control problem.

Kontakt:


Dr. Volker Kaibel 
Postanschrift:
Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Bereich Scientific Computing
Abteilung Optimierung
Takustr. 7
14195 Berlin-Dahlem


Tel.   : (+49 30) 84185-246
Fax    : (+49 30) 84185-269
e-mail : krumke@zib.de

Dr. Amin Coja-Oghlan 
Postanschrift
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin


Tel.   : (+49 30) 2093 3803
Fax    : (+49 30) 2093 3191
e-mail : coja@informatik.hu-berlin.de
zuletzt geändert am 12.09.2005 (alkox-www)