Integrality ratio for group Steiner trees and directed Steiner trees

Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang

Research output: Contribution to conferencePaper

24 Scopus citations

Abstract

We present an Ω(log2 k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs that are Hierarchically Well-Separated Trees, introduced by Bartal [Symp. Foundations of Computer Science, pp. 184-193, 1996], in which case this lower bound is tight. This relaxation appears to be the only one that have been studied for the problem, as well as for its generalization, the Directed Steiner Tree problem. For the latter problem, our results imply an Ω(log2 n/(log log n)2 n) integrality ratio, where n is the number of vertices in the graph. For both problems, this is the first known lower bound on the integrality ratio that is superlogarithmic in the input size. We also show algorithmically that the integrality ratio for Group Steiner Tree is much better for certain families of instances, which helps pinpoint the types of instances that appear to be most difficult to approximate.

Original languageEnglish (US)
Pages275-284
Number of pages10
StatePublished - Jan 1 2003
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998

Other

OtherConfiguralble Computing: Technology and Applications
CountryUnited States
CityBoston, MA
Period11/2/9811/3/98

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Integrality ratio for group Steiner trees and directed Steiner trees'. Together they form a unique fingerprint.

  • Cite this

    Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., & Wang, N. (2003). Integrality ratio for group Steiner trees and directed Steiner trees. 275-284. Paper presented at Configuralble Computing: Technology and Applications, Boston, MA, United States.