Research on graph algorithms

I did some unsuccessful research on approximation algorithms a few years ago, and later more fruitfully applied graph theory to logic. See my professional page.

Programming contest stuff

Highly recommended for contest preparation: the book “Programmation efficace” (in French, but at the time of writing, an English translation should come out in the near-ish future). It comes with a library of Python implementations of classical algorithms.

My own stuff:

I designed algorithmic exercises for Prologin 2015 and 2016, see here.


These are the best algorithms lecture notes ever. A way more pleasant read than CLRS!

Here are some implementations of simple algorithms. (Not very interesting…)

Some questions

What is the “essence” of the simplex algorithm, and how are its various variants (satisfiability of linear inequalities, effective Farkas Lemma, etc.) related?

Is there a simple combinatorial algorithm for (min-weight) perfect matching which doesn’t rely on blossoms? (It turns out that there is one for finding a unique perfect matching.)

How does duality in optimization (linear, Lagrangian, conic, Lasserre-Parrilo…) relate to negation in logic / category-theoretic duality? (If I recall correctly, Shin-ya Katsumata is interested in this question in the case of the Wasserstein metric.)