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)
Abstract: 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.