TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Thu, 01 Jun 2023 11:51:53 GMT2023-06-01T11:51:53Z5011Dense Steiner problems: approximation algorithms and inapproximabilityhttp://hdl.handle.net/11420/5996Title: Dense Steiner problems: approximation algorithms and inapproximability
Authors: Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
Abstract: 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.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/59962020-01-01T00:00:00Z