We study the multilevel 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 nonproportional 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), lρ}approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and l is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ ≈ 1.39, for example).
In this paper, we describe a natural generalization to the multilevel case of the classical (singlelevel) Steiner tree approximation algorithm based on Kruskal’s 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 multilevel Steiner tree problem with nonproportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multilevel instances derived from SteinLib.
more »
« less
LearningAugmented Algorithms for Online Steiner Tree
This paper considers the recently popular beyondworstcase algorithm analysis model which integrates machinelearned 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 worstcase 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.
more »
« less
 NSFPAR ID:
 10351515
 Date Published:
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 36
 Issue:
 8
 ISSN:
 21595399
 Page Range / eLocation ID:
 8744 to 8752
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Guruswami, Venkatesan (Ed.)Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worstcase bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δaccurate predictions where each predicted request matches the true request with probability δ, (2) listaccurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by listaccurate, and δaccurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for listaccurate predictions that are equivalent to the nonprediction setting, unless listaccurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.more » « less

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a blackbox, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rentorbuy problem, and show that incorporating optimization benchmarks directly in ML loss functions leads to significantly better performance, while maintaining a worstcase adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations, and posit that “learning for optimization” is a fertile area for future research.more » « less

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a blackbox, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rentorbuy problem, and show that incorporating optimization benchmarks directly in ML loss functions leads to significantly better performance, while maintaining a worstcase adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations, and posit that “learning for optimization” is a fertile area for future research.more » « less

Given a graph G = (V, E) and a subset T ⊆ V of terminals, a Steiner tree of G is a tree that spans T. In the vertexweighted Steiner tree (VST) problem, each vertex is assigned a nonnegative weight, and the goal is to compute a minimum weight Steiner tree of G. Vertexweighted problems have applications in network design and routing, where there are different costs for installing or maintaining facilities at different vertices. We study a natural generalization of the VST problem motivated by multilevel graph construction, the vertexweighted gradeofservice Steiner tree problem (VGSST), which can be stated as follows: given a graph G and terminals T, where each terminal v ∈ T requires a facility of a minimum grade of service R(v) ∈ {1, 2, . . . `}, compute a Steiner tree G0 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 0 with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multilevel 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 edgeweighted case, they have not been studied as well in the more general vertexweighted case. We first describe a simple heuristic for the VGSST problem whose approximation ratio depends on `, the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the VGSST 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) multigrade 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. Finally, we show that this problem is a special case of the directed Steiner tree problem and provide an integer linear programming (ILP) formulation for the VGSST problem.more » « less