ICS 2010

Navigation

Home
Committee
Call for papers
Attendees
Program
Photos
Comments
Important Dates
Submission
Accepted Papers
Accepted Posters
Camera-Ready
Student Grant
Registration
Visa Information
About ICS
Location/Accommodation
Contact
Sponsors
ITCS-Miniworkshop
About Beijing

Welcome to ICS2010

Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 42-48, 978-7-302-21752-7 Tsinghua University Press

A New Approach to Strongly Polynomial Linear Programming
Authors : Mihály Bárász and Santosh Vempala
[Download PDF]

Abstract:
We present an af_ne-invariant approach for solving linear programs. Unlike previous approaches, the potential strong polynomiality of the new approach does not require that graphs of polytopes have polynomial diameter (the Hirsch conjecture or weaker versions). We prove that two natural realizations of the approach work ef_ciently for deformed products [AZ99], a class of polytopes that generalizes all known dif_cult examples for variants of the simplex method, e.g., the Klee-Minty [KM72] and Goldfarb-Sit [GS79] cubes.

Preview: