Strong Steiner Tree Approximations in Practice

摘要: In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant ratio smaller than 2. The considered greedy and approaches based on linear programming involve the incorporation of k-restricted full components for some k ≥ 3. For most algorithms, their strongest theoretical bounds are only achieved → ∞. However, running time is also exponentially dependent k, so small tractable in practice.We investigate different implementation aspects parameter choices finally allow us to construct (somewhat) feasible practical use. We compare against each other, an exact algorithm integer programs, fast simple 2-approximations as well state-of-the-art heuristics.