Solving the Steiner Tree Problem with few Terminals
- URL: http://arxiv.org/abs/2011.04593v1
- Date: Mon, 9 Nov 2020 17:46:02 GMT
- Title: Solving the Steiner Tree Problem with few Terminals
- Authors: Johannes K. Fichte, Markus Hecher, Andre Schidler
- Abstract summary: A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm.
We enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*.
We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible function.
- Score: 8.024778381207128
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Steiner tree problem is a well-known problem in network design, routing,
and VLSI design. Given a graph, edge costs, and a set of dedicated vertices
(terminals), the Steiner tree problem asks to output a sub-graph that connects
all terminals at minimum cost. A state-of-the-art algorithm to solve the
Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner
algorithm. The algorithm builds a Steiner tree of the entire instance by
systematically searching for smaller instances, based on subsets of the
terminals, and combining Steiner trees for these smaller instances. The search
heavily relies on a guiding heuristic function in order to prune the search
space. However, to ensure correctness, this algorithm allows only for limited
heuristic functions, namely, those that satisfy a so-called consistency
condition. In this paper, we enhance the Dijkstra-Steiner algorithm and
establish a revisited algorithm, called DS*. The DS* algorithm allows for
arbitrary lower bounds as heuristics relaxing the previous condition on the
heuristic function. Notably, we can now use linear programming based lower
bounds. Further, we capture new requirements for a heuristic function in a
condition, which we call admissibility. We show that admissibility is indeed
weaker than consistency and establish correctness of the DS* algorithm when
using an admissible heuristic function. We implement DS* and combine it with
modern preprocessing, resulting in an open-source solver (DS* Solve). Finally,
we compare its performance on standard benchmarks and observe a competitive
behavior.
Related papers
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget.
Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
arXiv Detail & Related papers (2024-06-29T05:14:04Z) - Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
This paper focuses on the shortest path problem and the minimum Steiner tree problem.
We provide theoretical insights regarding the design of realizable hypothesis spaces for building scoring models.
Our experimental studies show that such problems can be solved to a decent extent with statistical significance.
arXiv Detail & Related papers (2024-02-03T17:05:01Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
The minimax algorithms for neural networks have been developed to solve many problems.
In this paper, we propose two types of minimax algorithms.
For the setting, we propose DRSGDA and prove that our method achieves a gradient.
arXiv Detail & Related papers (2023-02-08T01:42:45Z) - Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
We consider the Steiner tree problem on graphs where we are given a set of nodes.
The goal is to find a tree sub-graph that contains all nodes in the given set, potentially including additional nodes.
arXiv Detail & Related papers (2022-08-25T10:31:00Z) - CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial
Optimization Problems [0.0]
This paper proposes a search algorithm by expanding search space from a Markov chain to a depth limited tree based on SA.
At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of look ahead'
Our results show that above the primals SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.
arXiv Detail & Related papers (2022-03-09T10:07:26Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN$*$.
We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time)
Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13--55.89x, and existing parallel algorithms by at least an order of magnitude.
arXiv Detail & Related papers (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
We show that families of algorithms fail to produce nearly optimal solutions with high probability.
For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
arXiv Detail & Related papers (2020-04-25T05:45:59Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
We present a deterministic algorithm for non-in one-text variable Descent strongly-concave in the other.
We show that under the SGC assumption, the complexities of the algorithms match that of existing algorithms.
Results are presented in terms of oracle-texttZO-GDMSA and Numerical experiments are presented to support theoretical results.
arXiv Detail & Related papers (2020-01-22T00:05:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.