Hardness and approximation results for packing steiner trees |
| |
Authors: | Joseph Cheriyan Mohammad R Salavatipour |
| |
Affiliation: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Department of Computing Science, University of Alberta, T6G 2E8 Edmonton, Alberta, Canada |
| |
Abstract: | We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees.
For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint
Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a
hardness result of Θ(m
1/3/−ɛ) and give an approximation guarantee ofO(m
1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected
graphs.
Supported by NSERC Grant No. OGP0138432.
Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and
a University start-up fund at University of Alberta. |
| |
Keywords: | Steiner trees Packing problems Approximation algorithms Hardness of approximation |
本文献已被 SpringerLink 等数据库收录! |
|