Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs
191
0
0.0
(
0
)
Added by
Mateusz Lewandowski
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88 + epsilon$)-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain.
rate research
Read More
In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s in V$ and terminals $T subseteq V setminus {s}$, where each terminal $v in 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, krho}$-approximation [Charikar et al., 2004], and is hard to approximate with ratio $c log 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 $lceil log_2 |T| rceil + 1 le 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.
We study the behavior of an algorithm derived from the cavity method for the Prize-Collecting Steiner Tree (PCST) problem on graphs. The algorithm is based on the zero temperature limit of the cavity equations and as such is formally simple (a fixed point equation resolved by iteration) and distributed (parallelizable). We provide a detailed comparison with state-of-the-art algorithms on a wide range of existing benchmarks networks and random graphs. Specifically, we consider an enhanced derivative of the Goemans-Williamson heuristics and the DHEA solver, a Branch and Cut Linear/Integer Programming based approach. The comparison shows that the cavity algorithm outperforms the two algorithms in most large instances both in running time and quality of the solution. Finally we prove a few optimality properties of the solutions provided by our algorithm, including optimality under the two post-processing procedures defined in the Goemans-Williamson derivative and global optimality in some limit cases.
The prize-collecting Steiner tree problem PCSTP is a well-known generalization of the classical Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the latest (11th) DIMACS Challenge and since then a number of PCSTP solvers have been introduced in the literature, some of which drastically improved on the best results achieved at the Challenge. The following article aims to further advance the state of the art. It introduces new techniques and algorithms for PCSTP, involving various forms of reductions of PCSTP instances to equivalent problems---which for example allows to decrease the problem size or to obtain a better IP formulation. Several of the new techniques and algorithms provably dominate previous approaches. Further theoretical properties of the new components, such as their complexity, are discussed, and their profound interaction is described. Finally, the new developments also translate into a strong computational performance: the resulting exact solver outperforms all previous approaches---both in terms of run-time and solvability---and can solve formerly intractable benchmark instances from the 11th DIMACS Challenge to optimality.
Given a graph $G = (V,E)$ and a subset $T subseteq V$ of terminals, a emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v in T$ requires a facility of a minimum grade of service $R(v)in {1,2,ldotsell}$, compute a Steiner tree $G$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a $(2 ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service.
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+eps)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al (SWAT16) and adopting an approach by Chudak et al. (Math. Prog. 04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. 06). More generally, our approach readily gives a $( icefrac{4}{3}cdot r+eps)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Konemann et al. (Algorithmica~11) for partial cover problems. Together with a lower bound construction by Mestre (STACS08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a emph{non-black-box} fashion could not beat the factor $ icefrac{4}{3}cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
