Ben's short link page on k-supplier related works

For people who are interested in graph theory, here are a few links about the so-called "minimum k-supplier problem", a NP-hard problem applied to graphs... You know, one of those single-line defined problems fun to study, not easy to solve.

First, let us read a canonical definition of a minimum k-supplier set that can be found on Nada's unofficial compendium.

As a student, i looked to this problem and polynomial aproximation algorithms for its resolution. Then, with my teacher, we re-formulated the definition in a flavour that treats non complete graph and both the minimum k-supplier and the minimum k-center problems at a time. The idea is that we needed a pool of vertices and edges that were neither in the supplier set, neither concerned by the measure, just for use on the next chapter... Then, we used the bottleneck solving method proposed by D.Hochbaum and D.B. Shmoys and we tried to move to an incremental approach to the problem. This means that we would give a method that does not really work on graphs, but on graph differences. Thus, assuming our graph is moving, we defined a supplier editing cost an then an heuristic that minimize this cost while ensuring the next k-supplier is still as minimal as the previous one. The result is just an heuristic and has a limited set of scenarii where minimalisation was strongly proven. I think this now has been solved somewhere else and in a smarter way..

The fundation on which i relied on was the original formulation of the bottleneck method [Hochbaum/Shmoys] as presented in an article available in the ACM Journal of July 1986: "A Unified Approach to Approximation Algorithms for Bottleneck Problems" (with D. Shmoys), Journal of ACM, 33:3 (July 1986), 533-550."