New geometric techniques for linear programming and graph partitioning

In this thesis, we advance a collection of new geometric techniques for the analysis of combinatorial algorithms. Using these techniques, we resolve several longstanding questions in the theory of linear programming, polytope theory, spectral graph theory, and graph partitioning. The thesis consists of two main parts. In the first part, which is joint work with Daniel Spielman, we present the first randomized polynomial-time simplex algorithm for linear programming, answering a question that has been open for over fifty years. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. To do this, we begin by reducing the input linear program to a special form in which we merely need to certify boundedness of the linear program. As boundedness does not depend upon the right-hand-side vector, we run a modified version of the shadow-vertex simplex method in which we start with a random right-hand-side vector and then modify this vector during the course of the algorithm. This allows us to avoid bounding the diameter of the original polytope.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Kelner, Jonathan, 1980-

Advisor dc:contributor.advisor

• Daniel A. Spielman and Madhu Sudan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/38295

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/38295