[home] - [up]


Lectures and Colloquia during the semester



June 27, 2005

Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV           - map -
Lecture - 14.00 Uhr c.t.

Berthold Vöcking - RWTH Aaachen

Approximation Techniques for Utilitarian Mechanism Design

Abstract: We study the design of efficiently computable incentive compatible (or truthful) mechanisms for combinatorial optimization problems with multi-parameter agents. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques for NP-hard optimization problems do not fulfill these properties, we study alternative techniques.

For example, the well-known approach to transform pseudopolynomial algorithms into approximation schemes by rounding the objective function does not give monotone algorithms. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone approximation scheme. Our technique can be applied to various optimization problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. The monotone algorithm for the knapsack problem gives the first approximation scheme for single-minded multi-unit auctions.

The most efficient way to solve packing integer programs (PIPs) is LP-based randomized rounding. Unfortunately, also this techniques is not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions, unsplittable flow andmulticast routing.

joint work with Patrick Briest and Piotr Krysta


Colloquium - 16 Uhr s.t.

Oliver Klein -Freie Universität Berlin

Approximation Algorithms for the Earth Mover's Distance Under Transformations Using Reference Points

Abstract: The Earth Mover's Distance on weighted point sets is a distance measure with many applications. For those it is useful to have an estimation on the Earth Mover's Distance under various classes of transformations. For weighted point sets in the plane, we will show a 2-approximation algorithm for translations, a 4-approximation algorithm for rigid motions and an 8-approximation algorithm for similarity operations. The runtime of the translation approximation is O(TEMD(n,m)), the runtime of the latter two algorithms is O(nm TEMD(n,m)), where TEMD(n,m) is the time to compute the Earth Mover's Distance between two weighted point sets with n and m points, respectively. We will also show that these algorithms can be extended to arbitrary dimension. Unfortunately, this extension leeds to worse time- and approximation bounds.

All these algorithms are based on a more general structure, namely on reference points. We will also discuss reference points for weighted point sets with respect to the EMD.

This is joint work with Remco Veltkamp, Universiteit Utrecht.


[home] - [up] - [top]