Learning-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 for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.
Code (1)
Tasks
Steiner Tree ProblemSimilar Papers 제목 키워드 기반
GAT-Steiner: Rectilinear Steiner Minimal Tree Prediction Using GNNs
The Rectilinear Steiner Minimum Tree (RSMT) problem is a fundamental problem in VLSI placement and routing and is known to be NP-hard. Traditional RSMT algorithms spend a significant amount of time on finding Steiner poi…
Graph AttentionA Universal Error Measure for Input Predictions Applied to Online Graph Problems
We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online …
The 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 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 ProblemA Hierarchical Heuristic for Clustered Steiner Trees in the Plane with Obstacles
Euclidean Steiner trees are relevant to model minimal networks in real-world applications ubiquitously. In this paper, we study the feasibility of a hierarchical approach embedded with bundling operations to compute mult…