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

Petr Kolman, Jiří Sgall

Předchozí program semináře, letní semestr 2007 [Previous program, Spring 2007]

9. 5., 23. 5. 2007 (středa [Wednesday], 10:40, MFF UK Malá Strana S9)

Baruch Awerbuch, Rohit Khandekar, and Satish Rao: Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework. SODA'07.
(referuje Tomáš Ebenlendr)

Abstract: We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow 1+eps approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.

11. 4., 2. 5. 2007 (středa [Wednesday], 10:40, MFF UK Malá Strana S9)

Richard M. Karp and Robert Kleinberg: Noisy binary search and its applications. SODA'07.
(referuje Ondřej Zajíček)

Abstract: We study a noisy version of the classic binary search problem of inserting an element into its proper place within an ordered sequence by comparing it with elements of the sequence. In the noisy version we can not compare elements directly. Instead we are given a coin corresponding to each element of the sequence, such that as one goes through the ordered sequence the probability of observing heads when tossing the corresponding coin increases. We design online algorithms which adaptively choose a sequence of experiments, each consisting of tossing a single coin, with the goal of identifying the highest-numbered coin in the ordered sequence whose heads probability is less than some specified target value. Possible applications of such algorithms include investment planning, sponsored search advertising, admission control in queueing networks, college admissions, and admitting new members into an organization ranked by ability, such as a tennis ladder.

28. 3., 4. 4. 2007 (středa [Wednesday], 10:40, MFF UK Malá Strana S9)

C. Borgs, J. Chayes, L. Lovász, V.T. Sós, B. Szegedy and K. Vesztergombi:
Graph limits and parameter testing
. STOC 2006.
(referuje Marek Krčál)

Abstract: We define a distance of two graphs that reflects the closeness of both local and global properties. We also define convergence of a sequence of graphs, and show that a graph sequence is convergent if and only if it is Cauchy in this distance. Every convergent graph seq uence has a limit in the form of a symmetric measura ble function in two variables. We use these notions of distance and graph limits to give a general theo ry for parameter testing. As examples, we provide short proofs of the testability of MaxCut and the recent result of Alon and Shapira about the testability of hereditary graph properties.

14. 3., 21. 3. 2007 (středa [Wednesday], 10:40, MFF UK Malá Strana S9)

George Christodoulou, Elias Koutsoupias, and Angelina Vidali: A lower bound for scheduling mechanisms. SODA'07. Prezentace autorů.
(referuje Ondřej Zajíček)

Abstract: We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to 1+sqrt(2) for 3 or more machines.

28. 2., 7. 3. 2007 (středa [Wednesday], 10:40, MFF UK Malá Strana S9)

L. Epstein, A. Levin, G. J. Woeginger: Graph coloring with rejection. ESA'06.
(referuje Tomáš Ebenlendr)

We consider the following vertex coloring problem. We are given an undirected graph G=(V, E), where each vertex v is associated with a penalty rejection cost r_v. We need to choose a subset of vertices, V ', and to find a proper coloring of the induced subgraph of G over V'. We are interested in both the number of colors used to color the vertices of V', and in the total rejection cost of all other vertices.The goal is to minimize the sum of these two amounts. In this paper we consider both the online and the offline versions of this problem.In the online version, vertices arrive one at a time, revealing the rejection cost of the current vertex and the set of edges connecting it to previously revealed vertices. We also consider the classical online coloring problem on bounded degree graphs and on (k+1)-claw free graphs.