Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

On the Power of Discrete Helly Theorems and Lexicographic Helly Theorems

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login