Monday, April 23, 2012
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Lecture - 14:15
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
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.