Monday, April 23, 2012
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett
Lecture - 14:15
Abstract:
In this talk we overview some online problems on metric spaces and present
some recent results. First we deal with an online clustering problem where
the input is a sequence of points arriving one by one and our goal is
to divide them into clusters with minimal cost. The cost of a cluster
is the sum of a constant setup cost and the diameter.
In the second half of the talk we present some results about the online
k-server problem with rejection. Here there are k servers in a metric space
and the input is a sequence of points arriving one by one. After the
arrival of a request we have to move one of the servers to the request
point to serve it or we can reject it paying a penalty. The goal is to
minimize the sum of the total distance moved by the servers and the
penalties paid for the rejected requests. The presented results are joint
works with Emese Bittner, Janos Csirik, Gabriella Diveki, Leah Epstein,
Judit Nagy-Gyorgy, Asaf Levin.
Colloquium - 16:00
Abstract:
I am going to talk about combinatorial games played by two players, Alice
and Bob. The players alternately take turns. In each turn one vertex is
chosen. Alice starts. In the pizza game the graph is a cycle with
nonnegative weights assigned to the vertices. Alice can choose any vertex
in the first turn. In all other turns the player can choose a vertex if one
of its neighbors has been already taken. We proved a conjecture of Peter
Winkler by showing that Alice always has a strategy to obtain 4/9 of the
pizza. We described a linear time algorithm that computes Alice's strategy
and another algorithm that computes the optimal strategy for both players
in any possible position of the game in quadratic time.
Consider a generalization of the game on connected graphs with nonnegative
weights where one or both of the following rules apply: T- the subgraph
induced by the taken vertices is connected during the whole game; R- the
subgraph induced by the remaining vertices is connected during the whole
game. For any combinations of the rules and for any k we constructed
k-connected graphs where Bob has a strategy to gain almost all the weight.
We showed it is PSPACE-complete to decide who has the winning strategy if
condition R or both conditions T and R are required.
We also studied a game played on connected graphs without weights where
the first player who has no move satisfying T and R loses. And another
game where the first player who has no move satisfying T and R wins. We
showed that deciding who has the winning strategy is PSPACE-complete in
both games.
These results are joint work with Cibulka, Kyncl, Stolar and Valtr.