Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
239
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals $T$ require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals $u$, $v$ with priorities $P(u)$, $P(v)$ are connected using edges of rate $min{P(u),P(v)}$ or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio $c log log n$, where $n$ is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a $min{2(ln |T|+1), ell rho}$-approximation in this setting, where $rho$ is an approximation ratio for a heuristic solver for the Steiner tree problem and $ell$ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with $rhoapprox 1.39$, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskals minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i.e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
