Approximation Algorithms for Priority Steiner Tree Problems

Faryad Darabi Sahneh, Stephen Kobourov, Richard Spence

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the Priority Steiner Tree (PST) problem, we are given an undirected graph G= (V, E) with a source s∈ V and terminals T⊆ V\ { s}, where each terminal v∈ T requires a nonnegative priority P(v). The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from s to each terminal v consists of edges of rate greater than or equal to P(v). The PST problem with k priorities admits a min { 2 ln | T| + 2, kρ} -approximation [Charikar et al., 2004], and is hard to approximate with ratio clog log n for some constant c [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the (2 ln | T| + 2 ) -approximation to show an approximation ratio of ⌈ log 2| T| ⌉ + 1 ≤ 1.443 ln | T| + 2, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a (2 ln | T| + 2 ) -approximation using extensions of the spider decomposition by [Klein & Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings
EditorsChi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee
PublisherSpringer Science and Business Media Deutschland GmbH
Pages112-123
Number of pages12
ISBN (Print)9783030895426
DOIs
StatePublished - 2021
Event27th International Conference on Computing and Combinatorics, COCOON 2021 - Tainan, Taiwan, Province of China
Duration: Oct 24 2021Oct 26 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13025 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Computing and Combinatorics, COCOON 2021
Country/TerritoryTaiwan, Province of China
CityTainan
Period10/24/2110/26/21

Keywords

  • Approximation algorithms
  • Network design
  • Priority steiner tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Approximation Algorithms for Priority Steiner Tree Problems'. Together they form a unique fingerprint.

Cite this