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 Citations (Scopus)

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

Fingerprint

Steiner Tree
Integrality
Computer science
Steiner Tree Problem
Lower bound
Graph in graph theory
Computer Science
Denote
Imply

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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.
Halperin, Eran ; Kortsarz, Guy ; Krauthgamer, Robert ; Srinivasan, Aravind ; Wang, Nan. / Integrality ratio for group Steiner trees and directed Steiner trees. Paper presented at Configuralble Computing: Technology and Applications, Boston, MA, United States.10 p.
@conference{a2c7f1989487473abc07b7cad5e13d62,
title = "Integrality ratio for group Steiner trees and directed Steiner trees",
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.",
author = "Eran Halperin and Guy Kortsarz and Robert Krauthgamer and Aravind Srinivasan and Nan Wang",
year = "2003",
month = "1",
day = "1",
language = "English (US)",
pages = "275--284",
note = "Configuralble Computing: Technology and Applications ; Conference date: 02-11-1998 Through 03-11-1998",

}

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

Integrality ratio for group Steiner trees and directed Steiner trees. / Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, Nan.

2003. 275-284 Paper presented at Configuralble Computing: Technology and Applications, Boston, MA, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Integrality ratio for group Steiner trees and directed Steiner trees

AU - Halperin, Eran

AU - Kortsarz, Guy

AU - Krauthgamer, Robert

AU - Srinivasan, Aravind

AU - Wang, Nan

PY - 2003/1/1

Y1 - 2003/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038305624&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038305624&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0038305624

SP - 275

EP - 284

ER -

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