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.

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:

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?