Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 9, 2011

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 3.113 (1. Etage, Haus 3)

Lecture - 14:15

Rob van Stee - Max Planck Institut für Informatik, Saarbrücken

Truthful approximations for maximizing the minimum load

Designing truthful mechanisms for scheduling on related machines is a very important problem in single-parameter mechanism design. We consider the covering objective, that is we are interested in maximizing the minimum completion time of a machine. This problem falls into the class of problems where the optimal allocation can be truthfully implemented. A major open issue for this class is whether truthfulness affects the polynomial-time implementation.
We provide the first constant factor approximation for deterministic truthful mechanisms.
In particular we come up with a approximation guarantee of 2+epsilon for any epsilon>0, significantly improving on the previous upper bound of min(m,(2+epsilon)s_m/s_1). Here m is the number of machines and s_i is the speed of machine i for i=1,...,m.

Colloquium - 16:00

Piotr Sankowski - University of Warsaw

Min st-cut oracle for planar graphs with near-linear preprocessing time

For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log^5 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min st-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log^5 n) time and O(n log n) space and an explicit representation with additional O(C) time and space where C is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log^2 n) running-time factor.
Joint work with Glencora Borradaile and Christian Wulff-Nilsen.

Letzte Aktualisierung: 05.05.2011