Posts by Collection

publications

A Friendly Smoothed Analysis of the Simplex Method

Joint work with Daniel Dadush.

Published in 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018.

Full version to appear in siopt special issue (invited). Updated June 2019 to include a new algorithm, improving running time when σ is large.

PDF here. Slides here.

How Large is the Shadow? Smoothed Analysis of the Simplex Method

Thesis for the master’s programme Mathematical Sciences at Utrecht University. Finalist (top 3) for Faculty of Science master thesis prize.

PDF here.

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Joint work with Daniel Dadush, Bento Natura and László Végh.

PDF here. Slides here.

Smoothed Analysis of the Simplex Method

Joint work with Daniel Dadush.

Invited chapter in Beyond Worst Case Analysis (editor Tim Roughgarden), 2020+.

PDF here.

scans

Klee & Minty (1970) How Good Is the Simplex Method

Scanned from Inequalities : III : proceedings of the 3rd Symposium on inequalities held in Los Angeles, Sept. 1-9, 1969, edited by Oved Shisha. Pages 159-175. Often cited as Klee & Minty, How Good Is the Simplex Method?, 1970, Technical Report No. TR-22. Washington Univ Seattle Dept. of Mathmatics.

PDF here.

Borgwardt (1977) Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der linearen Optimierung

PhD thesis of K.H. Borgwardt. Scanned from the physical copy in the CWI library.

PDF here.

Kantorovich (1987) My journey in science

PDF here.

Borgwardt & Joas (1991) Cycling Examples for the Shadow Vertex Algorithm

I got this through snail mail from K.H. Borgwardt. Originally published as Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, Report No. 336.

PDF here.

Borgwardt & Joas (1992) Verbesserungen in der Laufzeitsanalyse des Simplexverfahrens

I got this through snail mail from K.H. Borgwardt. Originally published as Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, Report No. 419.

PDF here.