Integrality ratio for group Steiner trees and directed Steiner trees

摘要

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is Omega(log(2) k), where k denotes the number of groups; this holds even for input graphs that are hierarchically well-separated trees, introduced by Bartal [ in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184 - 193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an Omega(log(2) n/ (log log n)(2)) integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [ in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585 - 594] to show comparable inapproximability results, assuming that NP has no quasi-polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow-based relaxations) that appear to be most difficult to approximate.