Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/42026

Title: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Author: Hansen, Thomas Dueholm
Abstract: The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear programs (Klee-Minty examples). No non-polynomial lower bounds on the expected number of steps were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^(Omega(n^alpha)), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. Joint work with Oliver Friedmann and Uri Zwick.
Description: Presented on November 11, 2011 in Klaus 1116 Runtime: 62:08 minutes
Type: Lecture
Video
URI: http://hdl.handle.net/1853/42026
Date: 2011-11-11
Contributor: Georgia Institute of Technology. Algorithms, Randomness and Complexity Center
Aarhus universitet
Georgia Institute of Technology. School of Mathematics
Georgia Institute of Technology. School of Computer Science
Publisher: Georgia Institute of Technology
Subject: Simplex algorithm

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View Description
hansen.mp4 168.2Mb MPEG-4 video View/ Open Download Video
hansen_streaming.html 922bytes HTML View/ Open Streaming Video

This item appears in the following Collection(s)

Show full item record