Contraction-Based Steiner Tree Approximations in Practice

摘要: In this experimental study we consider contraction-based Steiner tree approximations. This class contains the only approximation algorithms that guarantee a constant ratio below 2 and still may be applicable in practice. Despite their vivid evolution theory, these have, to our knowledge, never been thoroughly investigated practice before, which is particularly interesting as most of algorithms' guarantees hold when some (constant) parameter k tends infinity, while running time exponentially dependent on very k. We investigate different implementation aspects choices finally allow us construct feasible for practical use. Then compare against each other state-of-the-art approaches.