# Research on graph algorithms

In 2016, I did a master’s internship with Christoph Dürr and Nguyễn Kim Thắng. We tried to design an approximation algorithm for the *online node-weighted Steiner forest problem*. Our approach didn’t work, but we improved our understanding of the difficulty of the problem.

- Slides of the defense
- Internship report / master’s thesis: under revision, available at some point in the future

During this internship, I also started investigating (independently of my advisors) a connection between *edge-colored graphs* and *linear logic proof nets*. The slides above outline some of my first rough ideas on this topic, including questions on sub-polynomial complexity classes. A more mature preprint on this topic will be made available soon.

# Programming contest stuff

Highly recommended for contest preparation: the book “Programmation efficace” (in French). 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 (Lagrangian, conic, or linear…) relate to negation in logic / category-theoretic duality?