### Abstract

We present an Ω(log^{2} 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 Ω(log^{2} 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 language | English (US) |
---|---|

Pages | 275-284 |

Number of pages | 10 |

State | Published - Jan 1 2003 |

Event | Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998 |

### Other

Other | Configuralble Computing: Technology and Applications |
---|---|

Country | United States |

City | Boston, MA |

Period | 11/2/98 → 11/3/98 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

### Cite this

*Integrality ratio for group Steiner trees and directed Steiner trees*. 275-284. Paper presented at Configuralble Computing: Technology and Applications, Boston, MA, United States.

}

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

Research output: Contribution to conference › Paper

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 -