Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

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