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:

• The AI which won Prologin 2013.
• Solutions for the Google Code Jam 2014 and for TaupIC 2011.
• Submissions in Haskell for Google Paris Hash Code 2014 (with Robin Morisset and Jonathan Laurent). Here’s an explanation in French; see the result for yourselves :-D
• My username in the Google Code Jam is coproduit.

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

Misc

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