arXiv ID: 2004.14102
Title: Dense Steiner problems: approximation algorithms and inapproximability
Language: English
Authors: Karpinski, Marek 
Lewandowski, Mateusz 
Meesum, Syed Mohammad 
Mnich, Matthias  
Issue Date: 2020
Publisher: Cornell University
Abstract (english): The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ |V(G)∖ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T₁,…,Tk are connected, and every terminal in Tᵢ has at least δ |Tⱼ| neighbours in Tⱼ, and at least δ|S| nodes in S = V(G)∖ (T₁∪…∪ Tk), for each i, j in {1,…, k} with i≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a ((13/12)+ε)-approximation algorithm for δ = 1/2 and any ε > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard.
URI: http://hdl.handle.net/11420/5996
Institute: Algorithmen und Komplexität E-11 
Type: Preprint (Vorabdruck)
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

35
Last Week
2
Last month
10
checked on Sep 22, 2020

Google ScholarTM

Check

Add Files to Item

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.