Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 12 Gennaio 2001  ore 12:00
One Line and n Points -- Analysis of LP-Related Randomized Processes
Prof. Emo Welzl
Institut für Theoretische Informatik, ETH Zürich

Dipartimento di Informatica e Sistemistica, DIS
via Salaria 113, II piano
Aula C2

Abstract:
We are given a finite set of points in the plane and a vertical directed line that does not have all points on one side. We want to find `ways' to the first edge connecting two points in the set met by the line. We analyze two randomized processes motivated by LP-related problems; in particular, if the appropriate higher-dimensional generalizatiions are considered. The first process describes what is known as the multiple pricing heuristics in linear programming, and it is a simplified variant of a previously analyzed algorithm by Clarkson. The second process describes the so-called random edge pivot rule for the simplex method. Since we illustrate the methods in the planar scenario, no geometric or LP-specific pre-knowledge is required. In fact, we will show that almost identical tools as we use them here appear, e.g., in minimum spanning tree computations. Joint work with B. Gartner, J. Solymosi, F. Tschirschnitz, and P. Valtr.