A robust and scalable algorithm for the Steiner problem in graphs
From MaRDI portal
Abstract: We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by quickly dealing with easier cases), but can also be used as a building block of an exact (branch-and-bound) algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
Recommendations
Cites work
- scientific article; zbMATH DE number 2089220 (Why is no real title available?)
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3677874 (Why is no real title available?)
- scientific article; zbMATH DE number 1538542 (Why is no real title available?)
- scientific article; zbMATH DE number 1926656 (Why is no real title available?)
- scientific article; zbMATH DE number 1424547 (Why is no real title available?)
- scientific article; zbMATH DE number 2209521 (Why is no real title available?)
- A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
- A dual ascent approach for steiner tree problems on a directed graph
- A faster approximation algorithm for the Steiner problem in graphs
- A hybrid GRASP with perturbations for the Steiner problem in graphs
- A hybrid heuristic for the \(p\)-median problem
- A note on two problems in connexion with graphs
- Algorithms for the maximum weight connected \(k\)-induced subgraph problem
- Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
- Dual heuristics on the exact solution of large Steiner problems
- Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
- Efficient path and vertex exchange in steiner tree algorithms
- Fast local search for the Steiner problem in graphs
- Improved algorithms for the Steiner problem in networks
- Matroids and integrality gaps for hypergraphic Steiner tree relaxations
- Measuring the impact of primal heuristics
- On Finding and Updating Spanning Trees and Shortest Paths
- Preprocessing Steiner problems from VLSI layout
- Reactive tabu search with path-relinking for the Steiner problem in graphs
- Rectilinear group Steiner trees and applications in VLSI design
- Reducibility among combinatorial problems
- Reduction tests for the steiner problem in grapsh
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- SCIP: solving constraint integer programs
- Solving Steiner tree problems in graphs to optimality
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- Steiner tree approximation via iterative randomized rounding
- Steiner's problem in graphs: Heuristic methods
- The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
- The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs
- Thinning out Steiner trees: a node-based model for uniform edge costs
- Tighter Bounds for Graph Steiner Tree Approximation
Cited in
(14)- A hybrid GRASP with perturbations for the Steiner problem in graphs
- Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
- Integer programming formulations for the shared multicast tree problem
- Implications, conflicts, and reductions for Steiner trees
- Implications, conflicts, and reductions for Steiner trees
- Decomposition methods for the two-stage stochastic Steiner tree problem
- Robust Algorithms for TSP and Steiner Tree
- Solving Steiner trees: Recent advances, challenges, and perspectives
- The rainbow Steiner tree problem
- Strong Steiner tree approximations in practice
- A fast algorithm for computing steiner edge connectivity
- The influence of preprocessing on Steiner tree approximations
- Swap-vertex based neighborhood for Steiner tree problems
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
This page was built for publication: A robust and scalable algorithm for the Steiner problem in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1646683)
