Sitemap

A list of all the posts and pages found on the site. For you robots out there is an XML version available for digesting as well.

Pages

Page Not Found

Page not found. Your pixels are in another canvas.

About me

About me

Archive Layout with Content

Posts by Category

Posts by Collection

Markdown

Page not in menu

This is a page not in th emain menu

Page Archive

Publications

Scans from the library

Sitemap

Posts by Tags

Terms and Privacy Policy

Blog posts

Posts

Future Blog Post

This post will show up by default. To disable scheduling of future posts, edit config.yml and set future: false.

Blog Post number 4

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 3

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 2

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

Blog Post number 1

This is a sample blog post. Lorem ipsum I can’t remember the rest of lorem ipsum and don’t have an internet connection right now. Testing testing testing this blog post. Blog posts are cool.

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.