Our Approximation Algorithm Library is Gaining Momentum

As theoreticians we usually tend to be over pessimistic about practical applicability of our results. This becomes even more visible in the area of approximation algorithms. It seems to be the case that algorithms with theoretical guarantees on approximation ratios are easily beaten by meta-heuristics like Simulated Annealing. Here, for example the recent 1.39-approximation algorithm for Steiner tree problem comes to mind. The algorithm, at first glance, seems too complicated to be implemented, and it seems that even if it was implemented it cannot deliver decent results in practice. However, both of these statements are only partially true. First of all, if one has the right tools, then implementing this algorithm is not impossible - the code developed by Maciej Andrejczuk can be seen here: http://siekiera.mimuw.edu.pl:8082/#/c/59/. (It is still undergoing some reviews, but should be shortly merged into the master branch.) The code is based on the iterative rounding framework we have developed in our approximation algorithms library: http://siekiera.mimuw.edu.pl/~paal/. The algorithm, when enhanced with some speed up heuristics, is able to solve reasonable size instances. Although, more improvements and tests are planned.

The other things we have implemented using the iterative rounding framework include 2-apprixmate solution to the tree augmentation problem, as well as the +1-approximation algorithm for the degree bounded spanning tree problem by Singh and Lau. Although, the second one of them still requires adding some documentation. On the other hand, we have developed a nice framework for local search algorithms that can be used to solve: TSP, capacitated and non-capacitated facility location k-median, as well as some greedy approximation algorithms. Finally, we are currently working on a framework for primal-dual algorithms, which could be used to implement several classical approximation algorithms. So stay tuned!