Ken Clarkson's Las Vegas Algorithms for Linear Programming
by Conor Meagher - cmeagh1@cs.mcgill.ca
Abstract
The purpose of this web page is to present Kenneth Clarkson's Las Vegas Algorithms for Linear Programming when the dimension is small. There is an iteractive applet that will allow the user to step through the algorithm to better understand it. This alogrithm runs in an expected time of O(d2n) + (d2log n)O(d)d/2 + O(1) + O(d4n1/2log n) as n approaches infinity.
Where n is the number of constraints, and d is the dimension of the Linear Program.
Definitions
An instance of a Linear Programming problem is:
Given a set of n half-spaces of d dimensions, and a given direction, find the maximum point in that direction that lies inside all the half-spaces.
This page assumes the reader is familiar with the simplex method.