### 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 |

### 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

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