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
8:00 - 9:00 Check-In/Light Breakfast (Hosted by IPAM)
9:00 - 9:50
Francisco Santos (University of Cantabria)

A counter-example to the Hirsch conjecture
PDF Presentation
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
PDF Presentation
2:30 - 3:00 Break
3:00 - 3:50
Günter Ziegler (Technische Universität Berlin)

On bad linear programs
PDF Presentation
4:00 - 6:00 Poster Session & Reception (Hosted by IPAM)

Wednesday, January 19, 2011

Morning Session
8:00 - 9:00 Continental Breakfast
9:00 - 9:50
10:00 - 10:30 Break
10:30 - 11:20
Bernd Gärtner (ETH Zürich)

Support Vector Machines meet Goldfarb Cubes
PDF Presentation
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
PDF Presentation
2:30 - 2:45 Break
2:45 - 3:35
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
10:00 - 10:30 Break
10:30 - 11:20
Oliver Friedmann (Ludwig-Maximilians-Universität München)

Subexponential Lower Bounds for the Simplex Algorithm
PDF Presentation
11:30 - 1:30 Lunch (on your own)

Afternoon Session
1:30 - 2:20
2:30 - 2:45 Break
2:45 - 3:35
Edward Kim (Technische Universiteit te Delft)

Some variations on connected layer families
PDF Presentation
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
PDF Presentation
10:00 - 10:30 Break
10:30 - 11:20
Jonathan Kelner (Massachusetts Institute of Technology)

Integral Geometry and the Polynomial Hirsch Conjecture
PDF Presentation
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)