Papers Steiner Tree Problem
“Steiner Tree Problem” 태그가 달린 논문 17편 · 필터 해제
Approximation Algorithms for Combinatorial Optimization with Predictions
We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization…
Combinatorial OptimizationSteiner Tree ProblemQuery-decision Regression between Shortest Path and Minimum Steiner Tree
Considering a graph with unknown weights, can we find the shortest path for a pair of nodes if we know the minimal Steiner trees associated with some subset of nodes? That is, with respect to a fixed latent decision-maki…
Decision MakingregressionSteiner Tree ProblemNeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios, often requiring intricate algorithmic design and exponential time. Recently, there has been growing interest in end-t…
Combinatorial OptimizationSteiner Tree ProblemDeep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem
The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks. In this paper, we present a study on solving the Euclide…
Graph Representation LearningRepresentation LearningSteiner Tree ProblemLearning to Prune Instances of Steiner Tree Problem in Graphs
We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes…
Steiner Tree ProblemIntegrating connection search in graph queries
Graph data management and querying has many practical applications. When graphs are very heterogeneous and/or users are unfamiliar with their structure, they may need to find how two or more groups of nodes are connected…
ManagementSteiner Tree ProblemSubmarine Cable Network Design for Regional Connectivity
This paper optimizes path planning for a trunkand-branch topology network in an irregular 2-dimensional manifold embedded in 3-dimensional Euclidean space with application to submarine cable network planning. We go beyon…
Steiner Tree ProblemLearning-Augmented Algorithms for Online Steiner Tree
This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model fo…
Steiner Tree ProblemVulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
Steiner Tree Problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices. It is a classic NP-hard combinatorial optimization problem and has many real-world applicatio…
Combinatorial OptimizationDeep Reinforcement LearningGraph Embeddingreinforcement-learning+2The Power of Many: A Physarum Swarm Steiner Tree Algorithm
We create a novel Physarum Steiner algorithm designed to solve the Euclidean Steiner tree problem. Physarum is a unicellular slime mold with the ability to form networks and fuse with other Physarum organisms. We use the…
Steiner Tree ProblemSolving Large Steiner Tree Problems in Graphs for Cost-Efficient Fiber-To-The-Home Network Expansion
The expansion of Fiber-To-The-Home (FTTH) networks creates high costs due to expensive excavation procedures. Optimizing the planning process and minimizing the cost of the earth excavation work therefore lead to large s…
Evolutionary AlgorithmsSteiner Tree ProblemComputing Steiner Trees using Graph Neural Networks
Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problem…
Graph AttentionGraph GenerationGraph LearningSteiner Tree Problem+1Solving the Steiner Tree Problem with few Terminals
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 th…
Steiner Tree ProblemDevolutionary genetic algorithms with application to the minimum labeling Steiner tree problem
This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of r…
Combinatorial OptimizationEvolutionary AlgorithmsSteiner Tree ProblemvalidEvolutionary framework for two-stage stochastic resource allocation problems
Resource allocation problems are a family of problems in which resources must be selected to satisfy given demands. This paper focuses on the two-stage stochastic generalization of resource allocation problems where futu…
Steiner Tree ProblemVocal Bursts Valence PredictionSolving the Steiner Tree Problem in graphs with Variable Neighborhood Descent
The Steiner Tree Problem (STP) in graphs is an important problem with various applications in many areas such as design of integrated circuits, evolution theory, networking, etc. In this paper, we propose an algorithm to…
Steiner Tree ProblemDynASP2.5: Dynamic Programming on Tree Decompositions in Action
A vibrant theoretical research area are efficient exact parameterized algorithms. Very recent solving competitions such as the PACE challenge show that there is also increasing practical interest in the parameterized alg…
Steiner Tree Problem