Randomized Pivot Algorithms in Linear Programming

Lukas Finschi

1997 February 28

Download: PDF, PS, PS.gz

Abstract

The study of algorithms in linear programming has produced in the last years remarkable developments; especially randomization has led to new bounds for the (expected) computation time. An algorithm of Matousek, Sharir, and Welzl (as well as similar algorithms, e.g. of Kalai) established a subexponential upper bound for the expected run time of a class of abstract optimization problems (we call them optimization problems of LP-type). The first chapter of this diploma thesis contains a strict discussion of the axiomatic framework of this class and the analysis of the mentioned algorithm of Matousek, Sharir, Welzl; in addition we discuss in the same way a sampling technique of Clarkson which improves the subexponential bound further.

It is well known that in general a linear programming problem does not hold the axioms of the LP-type framework: The socalled locality condition will usually fail when the solution of the linear program is not unique. When the feasible region of the LP is bounded, then this problem can be easily solved; the unbounded case is more difficult. The common way out is the use of a numerical bounding box; in this thesis we develop a technique with a combinatorial bounding box (see chapter 2) where the size of the box is represented by a parameter which is considered to be large (but we never set this parameter to a concrete value): We will not have no compute a concrete numerical bound such that the box is large enough for a given LP, also there are no huge numbers which come into computation; our technique is purely combinatorial and enables to design combinatorial algorithms.

The studies in chapter 1 and 2 are necessary for the design and analysis of the pivot algorithms in the third chapter; especially we discuss again the algorithm of Matousek, Sharir, Welzl. An implementation of this algorithm in the C programming language demonstrates the concrete application of our techniques in practice.

We conclude this thesis by reporting some experiences from the experiments with our implementation and try to give some suggestions for the further research.