The General Steiner Tree-Star problem.
type: Item
instance of: scholarly article
title: The General Steiner Tree-Star problem.
zbMATH Open document ID: 1042.68120
DOI: 10.1016/S0020-0190(02)00271-5
author: Samir Khuller
author: An Zhu
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: The Steiner tree problem is defined as follows -- given a graph \(G=(V,E)\) and a subset \(X\subset V\) of terminals, compute a minimum cost tree that includes all nodes in \(X.\) Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a ``switch'' cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set \(X\) cannot be connected to each other directly but only via the Steiner nodes \(V\backslash X,\) is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of \(\Theta(\ln n)\) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of \(5.16\) and \(5.\)
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856478
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Facility location
zbMATH Keywords: Steiner trees
MaRDI profile type: Publication
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Q3840357
cites work: The Steiner tree problem
cites work: Greedy Strikes Back: Improved Facility Location Algorithms
cites work: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
cites work: Provisioning a virtual private network
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: A Branch and Cut Algorithm for a Steiner Tree-Star Problem
cites work: Q4526991
full work available at URL: s0020-0190(02)00271-5
OpenAlex ID: W2045906087
description: scientific article; zbMATH DE number 1856478