Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, January 24, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Nir Halman (Technion, Haifa)
It is well known that there is a strong relation between Helly theorems and LP-type programming (a generalization of Linear Programming).
We introduce the idea of discrete Helly theorems and relate them to a new kind of discrete optimization problems - discrete LP-type (DLP) problems. An example of a discrete Helly theorem is this: Let D be a set of unit intervals on the real line, and S be a set of points. If every set of p+1 intervals from D can be pierced by p points from S, then the entire set D of intervals can be pierced by p points from S. The corresponding optimization problem is just the p-center problem for the midpoints of the intervals in D, where the centers are restricted to be from S. We give numerous new discrete Helly numbers.
We show that from every fixed-dimensional DLP problem one can get a discrete Helly theorem. Moreover, under certain conditions, discrete Helly theorems yield fixed-dimensional DLP problems. We develop random algorithms to solve these DLP problems in linear time and apply them to solve optimization problems in the fields of location theory and computational geometry such as the discrete p-center problem on the real line mentioned above.
Time permitting, we will also discuss lexicographic Helly theorems and their relation to (standard) LP-type problems.
The talk is based upon a paper which appeared in FOCS 2004.
Automatic MiSe System Software Version 1.4803M | admin login