Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? - IPAM

Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

January 18 - 21, 2011

Schedule

All times in this Schedule are Pacific Time (PT)

Tuesday, January 18, 2011

Morning Session

08:00-09:00
Check-In/Light Breakfast (Hosted by IPAM)
09:00-09:50
Francisco Santos (University of Cantabria)
A counter-example to the Hirsch conjecture
10:00-10:30
Break
10:30-11:20
Fred Holt (University of Washington)
Images of paths
11:30-13:30
Lunch (on your own)

Afternoon Session

13:30-14:20
David Bremner (University of New Brunswick)
Geodesic EmBeddings of Path Complexes
14:30-15:00
Break
15:00-15:50
Günter Ziegler (Technische Universität Berlin)
On bad linear programs
16:00-18:00
Poster Session & Reception (Hosted by IPAM)

Wednesday, January 19, 2011

Morning Session

08:00-09:00
Continental Breakfast
09:00-09:50
David Avis (Kyoto University)
History based pivot rules for acyclic USOs on hypercubes
10:00-10:30
Break
10:30-11:20
Bernd Gärtner (ETH Zürich)
Support Vector Machines meet Goldfarb Cubes
11:30-13:30
Lunch (on your own)

Afternoon Session

13:30-14:20
Tamás Terlaky (Lehigh University)
Algorithms and Conjectures for Linear Optimization
14:30-14:45
Break
14:45-15:35
Komei Fukuda (ETH Zürich)
Walking on the arrangement, not on the feasible region
15:45-16:00
Break
16:00-16:50
Yuriy Zinchenko (University of Calgary)
Polytopes and Arrangements: Diameter and Curvature

Thursday, January 20, 2011

Morning Session

08:00-09:00
Continental Breakfast
09:00-09:50
Yinyu Ye (Stanford University)
The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
10:00-10:30
Break
10:30-11:20
Oliver Friedmann (Ludwig-Maximilians-Universität München)
Subexponential Lower Bounds for the Simplex Algorithm
11:30-13:30
Lunch (on your own)

Afternoon Session

13:30-14:20
Jim Renegar (Cornell University)
Central Swaths (a generalization of the central path)
14:30-14:45
Break
14:45-15:35
Edward Kim (Technische Universiteit te Delft)
Some variations on connected layer families
15:45-16:00
Break
16:00-16:50
Sergei Chubanov (Universität-GHS Siegen)
A polynomial relaxation-type algorithm for linear programming

Friday, January 21, 2011

Morning Session

08:00-09:00
Continental Breakfast
09:00-09:50
Nicolai Hähnle (École Polytechnique Fédérale de Lausanne (EPFL))
An abstract view on the polynomial Hirsch conjecture
10:00-10:30
Break
10:30-11:20
Jonathan Kelner (Massachusetts Institute of Technology)
Integral Geometry and the Polynomial Hirsch Conjecture
11:30-13:30
Lunch (on your own)

Afternoon Session

13:30-14:20
Annamaria Amenta (University of California, Davis (UC Davis))
Complexity of Delaunay Triangulation
14:30-15:00
Break
15:00-15:50
Santosh Vempala (Georgia Institute of Technology)
An Affine-invariant Algorithm for Linear Programming
Printable Version