IPAM Institute for Pure and Applied Mathematics UCLA NSF
Skip Navigation Links

Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

January 18 - 21, 2011

IPAM Building

Printable Version

Tuesday, January 18, 2011

Morning Session

8:00 - 9:00 Check-In/Breakfast (Hosted by IPAM)
9:00 - 9:50

Francisco Santos (University of Cantabria)

"A counter-example to the Hirsch conjecture"
Presentation (PDF File)

10:00 - 10:30 Break
10:30 - 11:20

Fred Holt (University of Washington)

"Images of paths"

11:30 - 1:30 Lunch (on your own)

Afternoon Session

1:30 - 2:20

David Bremner (University of New Brunswick)

"Geodesic EmBeddings of Path Complexes"
Presentation (PDF File)

2:30 - 3:00 Break
3:00 - 3:50

Günter Ziegler (Technische Universität Berlin)

"On bad linear programs"
Presentation (PDF File)

4:00 - 6:00 Reception (Hosted by IPAM) & Poster Session

Wednesday, January 19, 2011

Morning Session

8:00 - 9:00 Continental Breakfast
9:00 - 9:50

David Avis (Kyoto University)

"History based pivot rules for acyclic USOs on hypercubes "
Presentation (PDF File)

10:00 - 10:30 Break
10:30 - 11:20

Bernd Gärtner (ETH Zürich)

"Support Vector Machines meet Goldfarb Cubes"
Presentation (PDF File)

11:30 - 1:30 Lunch (on your own)

Afternoon Session

1:30 - 2:20

Tamás Terlaky (Lehigh University)

"Algorithms and Conjectures for Linear Optimization "
Presentation (PDF File)

2:30 - 2:45 Break
2:45 - 3:35

Komei Fukuda (ETH Zürich)

"Walking on the arrangement, not on the feasible region"
Presentation (PDF File)

3:45 - 4:00 Break
4:00 - 4:50

Yuriy Zinchenko (University of Calgary)

"Polytopes and Arrangements: Diameter and Curvature"
Presentation (PowerPoint File)


Thursday, January 20, 2011

Morning Session

8:00 - 9:00 Continental Breakfast
9:00 - 9:50

Yinyu Ye (Stanford University)

"The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate"
Presentation (PDF File)

10:00 - 10:30 Break
10:30 - 11:20

Oliver Friedmann (Ludwig-Maximilians-Universität München)

"Subexponential Lower Bounds for the Simplex Algorithm"
Presentation (PDF File)

11:30 - 1:30 Lunch (on your own)

Afternoon Session

1:30 - 2:20

Jim Renegar (Cornell University)

"Central Swaths (a generalization of the central path)"
Presentation (PDF File)

2:30 - 2:45 Break
2:45 - 3:35

Edward Kim (Technische Universiteit te Delft)

"Some variations on connected layer families"
Presentation (PDF File)

3:45 - 4:00 Break
4:00 - 4:50

Sergei Chubanov (Universität-GHS Siegen)

"A polynomial relaxation-type algorithm for linear programming"
Presentation (PowerPoint File)


Friday, January 21, 2011

Morning Session

8:00 - 9:00 Continental Breakfast
9:00 - 9:50

Nicolai Hähnle (École Polytechnique Fédérale de Lausanne (EPFL))

"An abstract view on the polynomial Hirsch conjecture"
Presentation (PDF File)

10:00 - 10:30 Break
10:30 - 11:20

Jonathan Kelner (Massachusetts Institute of Technology)

"Integral Geometry and the Polynomial Hirsch Conjecture"
Presentation (PDF File)

11:30 - 1:30 Lunch (on your own)

Afternoon Session

1:30 - 2:20

Annamaria Amenta (University of California, Davis (UC Davis))

"Complexity of Delaunay Triangulation"

2:30 - 3:00 Break
3:00 - 3:50

Santosh Vempala (Georgia Institute of Technology)

"An Affine-invariant Algorithm for Linear Programming"
Presentation (PowerPoint File)

NSF Math Institutes   |   Webmaster