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