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.

In smoothed analysis, we study the running time of an algorithm after adding a small amount of random noise to an arbitrary problem instance. Even if the worst-case running time is bad, the smoothed running time might be good. This would indicate that the worst-case instances are pathological and brittle, thus hopefully explaining good practical performance.

The simplex method is one algorithm for which smoothed analysis was very succesful. In this paper, we significantly improve earlier smoothed complexity bounds. We do this with a much cleaner and simpler proof than previous analyses.

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. Talk 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.

Published in 52th Annual ACM SIGACT Symposium on Theory of Computing, 2020.

The classical analysis of polynomial time LP solving results in iteration bounds depending on the bit complexity of the input data. Later work by Tardos and by Vavasis and Ye established bounds depending only on a certain condition number of the constraint matrix.

We describe an algorithm whose running time instead depends on an arbitrarily much better (smaller) condition number of the constraint matrix, and give an analysis improving the dependence on the dimension of the problem. Moreover, we describe a novel approximation method for the involved condition numbers and find an algorithm to rescale the constraint matrix to approximately minimize the condition number.

PDF here. Talk here.

Smoothed Analysis of the Simplex Method

Joint work with Daniel Dadush.

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

We describe the key ideas in smoothed analysis of the simplex method. We illustrate these ideas by bounding the smoothed complexity of the convex hull in two dimensions.

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.