Show simple item record

dc.contributor.authorHansen, Thomas Dueholmen_US
dc.descriptionPresented on November 11, 2011 in Klaus 1116en_US
dc.descriptionRuntime: 62:08 minutesen_US
dc.description.abstractThe 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.en_US
dc.format.extent62:08 minutesen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesARC Theory Dayen_US
dc.subjectSimplex algorithmen_US
dc.titleSubexponential lower bounds for randomized pivoting rules for the simplex algorithmen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameAarhus universiteten_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Mathematicsen_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Computer Scienceen_US

Files in this item


This item appears in the following Collection(s)

  • ARC Theory Day [5]
    Thursday, November 10, 2011 and Friday, November 11, 2011

Show simple item record