Approximation algorithms for combinatorial optimization with predictions
Authors: Antonios Antoniadis
Marek Elias
Adam Polak
Moritz Venzin
Venue: ICLR 2025 Spotlight (2025)
Keywords: Approximation Algorithm
Predictions
ML-augmented
Combinatorial Optimization
Primary area: optimization
TL;DR: We give near-linear time learning-augmented (1+eta/OPT)-approximation algorithms for a number of problems, including Vertex Cover, Steiner Tree, Minimum Weight Perfect Matching, Knapsack, and Maximum Clique.

Abstract: We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a generic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear-time algorithms for, e.g., Vertex Cover, Steiner Tree, Minimum Weight Perfect Matching, Knapsack, and Maximum Clique. Our algorithms produce an optimal solution when provided with perfect predictions and their approximation ratio smoothly degrades with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond the reach without predictions in given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.

Published as a conference paper at ICLR 2025
APPROXIMATION ALGORITHMS FOR COMBINATORIAL OPTIMIZATION WITH PREDICTIONS*
Antonios Antoniadis
University of Twente, Enschede, Netherlands a. suttotte
Marek Eliáš Adam Polak Moritz Venzin
Bocconi University, Milan, Italy (marek. eliass, adam. polak, moritz.
ABSTRACT
We initiate systematic study of utilizing predictions to improve over approxima- tion guarantees of classic algorithms, without increasing the running time. We propose systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple meea-))ineaar time algorithms for, e.g., Vertex Cover, Steiner Tree, Win-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough pre- diction error achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX- hardness of many of the above problems. Although we show optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem.
approach be
INTRODUCTION
Combinatorial optimization studies problems of selecting an optimal solution, with respect to a given cost function. from discrete set of potential solutions. This framework is ubiquitous, both in theory and in practice, finding application in a vast number of areas, e.g., resource allocation, machine learning, efficient networks, logistics. However, these problems are typically NP-hard, and hence they cannot be solved to optimality in polynomial time (unless P equals NP). It is thus necessary develop efficient algorithms even if this comes at the cost of relaxing the optimality requirement. This trade-off between optimality and tractability is the main paradigm of the (classic) theory of approximation algorithms, see, e.g., (Williamson and Shmoys, 2011).
Despite the success of the classic analysis of approximation algorithms, its distinction between tractable and intractable problems often too crude. Indeed, for modern big data applications, running time polynomial in the input size can hardly be considered efficient, as we often require algorithms with a running time that a small polynomial or even linear in the input size. This more fine-grained point of view algorithm design has received considerable attention in recent years, Many combinatorial optimization problems (e.g., Vertex Cover, Steiner Tree, or Knapsack) admit simple and fast (near- Jlinear time constant-factor approximation algorithms Beauuae and Even, 1981; Mehlhorn, 1988; Dantzig, 1957), but improving upon their approximation guarantees often seems require significantly more running time (sometimes even exponentially, Vertex Cover (Khot and Regev, 2008)). However, it is important to note that such limitations are based on worst-case analysis, and do not necessarily represent the difficulty of typical instance.
the case for
It is natural to expect that instances arising in practice can be modelled as coming from a fixed distribution, making them amenable machine-learning techniques. Using historic input data and
"The full version of the paper available rxi www.v.org/abb////// 16600.

---

Published as a conference paper at ICLR 2025
some (possibly computationally expensive) training, we can hope to guide efficient algorithm with poor (worst-case) approximation guarantee to obtain near-optimal solutions.
1.1 OUR CONTRIBUTION
In this paper, we initiate a systematic study of utilizing predictions to improve over the approximation guarantees of classic algorithms without increasing the running time. This approach fits the current line of research on utilizing predictions to improve performance of algorithms, started by the seminal papers of Kraska al. (2018) and Lykouris and Vassilvitskii (2021). We focus broad class of optimization problems, which we call selection problems, and which captures many fundamental problems in combinatorial optimization, e.g., Set Cover, Travelling Salesperson Problem (TSP), Steiner Tree, or Knapsack.
Definition (Selection problem). We are given n. items, numbered with integers from [n]] = f1,2.... n.,, with non-negative weights w: [n] + Rz0 and an implicit collection X S 2 of feasible subsets of items. Our task is to find feasible solution X E X minimizing (or maximizing) its total weight wx(]] == Eiex w(i))
Note that the complexity of this task comes from the size of X, which usually exponential in n.
Our work considers the offline setting, where the whole input is available to the algorithm from the start. This is in contrast to much the to-date research on learning-augment which focuses online problems, where the input is not known to the algorithm in advance and the predictions are used to decrease uncertainty about the future (see the survey of Mitzenmacher and Vassilvitskii (2020)). So far, offline problems were studied mostly in the warm- start setting, where predictions in the form of solutions to past instances are used to speed up exact algorithms (see Section 1.4 on related work). The foeus of such works is on the dependence between the running time and the quality of the predictions.
algorithms,
Our target is to maintain superb running time in all situations, and we study the dependence of approximation ratio on the prediction quality. Having access to past instances, one can hope to learn which items are likely to be part of an optimal solution and provide the set of such items to the algorithm as a prediction. Utilizing such prediction comes with two main challenges.
(I) The predicted set of items may be infeasible. Ensuring feasibility of solutions produced by deep-lcarning models is challenging problem, and enforcing even simple combinatorial constraints requires very complex neural architectures (Bengio al., 2021). In order to utilize potentially infeasible predictions effectively, we need algorithms that can transform the prediction into a feasible solution without discarding the correct parts of the prediction. We carefully design a black-box mechanism that turns any approximation algorithm into leamning-augmente algorithm (utilizing possibly infeasible predictions) whose approximation ratio smoothly deteriorates with increasing prediction error. Our approach gives (near- Jlinear time algorithms for many problems, e.g., Vertex Cover, Steiner Tree, Min- Wei-Wt Perfect Matching, Knapsack, and Clique.
(2) The predicted of items may contain costly mispredictions. When given mostly correct prediction, it is certainly possible to detect a single mispredicted item with a huge weight, say, larger than the total weight of the optimal solution. Our goal is to push this idea to its limits by detecting mispredictions which are as small as possible. We study this challenge on the case of the Steiner Tree problem. We develop an algorithm that can detect and eliminate mispredictions of cost larger than the cost of single connection between pair of terminals in an optimal solution.
1.2 OUR RESULTS IN MORE DETAIL
Before stating our results formally, we have to define two crucial quantities: the approximation ratio and the prediction error.
Approximation ratio. We measure the quality of solutions produced by approximation algorithms using the standard notion of approximation ratio. For minimization problems, we say that an algorithm is p-approximation algorithm if we are always guaranteed that w(X) & p w(X"), where X denotes the solution returned by the algorithm, and X denotes an optimal solution for the same instance. Analogously, for maximization problems, p-approximate algorithm always satisfies
2

---

Published as a conference paper at ICLR 2025
(xX) p. =(("). We refer to p as the approximation ratio. For minimization problems have p > and smaller ratios are better; for maximization problems p E [0, 1] and larger ratios are better.
Prediction and prediction error. The prediction received by our algorithms is an arbitrary (not necessarily feasible) set of items X _ [n]. We say that X has error (n** ,n") with respect to solution X, if
1y* == wr X), and 7f q := = X),
i.e., ry+ the total weight of false positives, and nT is the total weight of false negatives. Usually we consider the prediction error with respect to an optimal solution, denoted by X We note that such predictions are PAC-learnable (see Section 1.3). In our performance bounds, the prediction error can be always considered with respect to the closest optimal solution.
Let us also remark that an alternative setting, where each item E [r] is associated with fractional prediction p; E [0, IJ (supposed to denote the a confidence that is part of the optimal solution), is actually equivalent to the setting we consider. Indeed, one can convert such fractional predictions to a set X with simple randomized rounding (adding each item to X independently with probability p:) and the expected value of the prediction error stays the same.
Minimization problems. Let II be problem of selecting a feasible solution E X' of minimum total weight. In Section 2, we show black-box approach to turn any off-the-shelf p-approximation algorithm A for IT into learnin--ugmmetedd algorithm for with approximation ratio
1j + (p 1).77
1 1
OPT
Here, (17 .7 denotes the error of the prediction X given to the algorithm with respect to optimal solution X of weight OPT == w(X*). The asymptotic running time the resulting algorithm is the same as that of A.
To gain some intuition about the above approximation ratio guarantee, note that for the trivial prediction X = @ we have 17 0 and 7 OPT, and in turn 1 + (n* + (p 1) 17 "/OP/TTTT p. which squarely corresponds to simply running the (prediction-less algorithm A. This shows that the p factor in front of 17 is necessary.
In Section 2.1 we give several examples of how this black-box approach can be applied in order approximation algorithms for some fundamental
to obtain (near-)line mear-)linear time problems in combinatorial optimization, namely Minimum (and Min- Weight Vertex Cover, Minimum (and Min-Weight) Steiner Tree, and Min-Weight Perfect Matching (in graphs with edge weights satisfying the triangle inequality).
Maximization problems. Section 3 we give a similar result for maximization problems. Let II be problem of selecting set maximizing the total weight from the collection of sets of items X. Let be a p-approximation algorithm for the corresponding complementary problem of selecting a set minimizing the total weight over sets of items Y such that ([n] \ ()) X. We construct algorithm for IT with running time asymptotically the same as that of A and with approximation ratio
(p 1) n + 1
OPT
given predictions of error ()+ with respect optimal solution X of weight OPT w wXX)).
Even though the notion of the complementary problem may not seem intuitive at first, we note that for many natural problems the complementary problem also happens to be natural and well studied problem, e.g., Vertex Cover is the complementary problem of Independent Set. In Section 3. we elaborate on how apply our black-box construction Clique and Knapsack.
Lower bounds. In the full version of the paper (Antoniadis et al., 2024), we show that our black-box approach from Sections and 3, despite being simple, cannot be improved for the class of selection problems as whole. More specifically, regarding minimization problems, Vertex Cover problem with predictions, any (polynomial-tin -imee soamiing-uummntte algorithm with an approximation ratio with better dependence the prediction error would contradict the Unique
show that for the
3

---

Published as a conference paper at ICLR 2025
Games Conjecture (UGC), which is standard assumption in computational complexity but to the best of our knowledge has not been used before in the context of Regarding maximization problems, give similar UGC-based lower bound for the Clique and Independent Set problems.
algorithms.
Refined algorithm for Steiner Tree. Although our lower bounds are tight for the considered classes of combinatorial optimization problems as a whole, they do not rule out refined upper bounds, e.g., for specific problems or in terms of other (more fine-grained) measures of prediction errors. In Section we propose such a refined algorithm for the Steiner Tree problem. In this problem, a small number of false positives with large weight can have large impact on the performance of our generic black-box algorithm from Section 2. Our refined algorithm is guided by hyperparameter in order to detect and avoid false positives with high weight. It is based a 2-approximation algorithm called the MST heuristic (Kou et al., 1981; Mehlhorn, 1988). The contribution of false positives to our algorithm's 's performance guarantee depends only on their number, and not on their weights, and it is capped by the cost of individual connections made by the MST heuristic (without predictions). The final approximation guarantee follows from a careful analysis of how the output of our algorithm converges to the prediction as its hyperparameter a increases. We also show that our analysis of this algorithm is tight.
Experimental results. The full version of the paper (Antoniadis et al., 2024) contains an experimen- tal evaluation' of our refined Steiner Tree algorithm on graphs from the PACE 2018 Challenge (Bonnet and Sikora, 2018), using as a benchmark the winning Steiner Tree solver from that challenge (Ruiz al., 2018). These experiments allow us to better understand the impact of the hyperparameter on the performance of our algorithm. They also demonstrate that (for sufficiently concentrated input distribution) we can find near-optimal solutions in time in which conventional algorithms can achieve only rough approximations.
1.3 FURTHER REMARKS ON OUR SETTING
Learnability. The predictions that our algorithms require are PAC-lcamable via the following simple argument. First, since the space of possible predictions is finite and its size is single exponential in n, it suffices to perform empirical risk minimization (ERM) on a polynomial number of samples (see, e.g., Polak and Zub (2024, Theorem 5)). Second, ERM for the combined prediction error 1yt + 1 boils down to taking a coordinate-wise majority vote of solutions to the sampled instances. We use this approach in our experiments in the full version of the paper (Antoniadis et al., 2024).
At the same time, our setting is flexible enough to allow for other methods of generating predictions. For instance, it is not hard to imagine a deep-learning model that assigns to each input element the probability that it belongs to an optimal solution (Joshi et al., 2019; Ahn et al., 2020). Then, a prediction can be obtained by sampling each element with the assigned probability.
We remark that any such learning likely to be computationally expensive, but this should come then be utilized by our mamming-auggented
at surprise, because the resulting predictions algorithms to "break" known lower bounds. The time saved this way must be spent somewhere else, i.e., during learning. The advantage is that, when we are repeatedly solving similar recurring instances, this costly learning process is performed only once, and the resulting predictions can be (re-)used multiple times.
Infeasible predictions. We stress out that it is an absolutely crucial characteristic of our work that our algorithms accept predictions sets that are not necessarily feasible solutions. 2 Bengio et al. (2021) argue that ensuring feasibility of predictions significantly increases the complexity of the learning process, with difficulties specific to different types of combinatorial constraints. Accepting infeasible predictions allows for simpler and possibly more versatile learning approaches like the ones outlined in the previous paragraphs.
th sh-predi et ooss 'It is common characteristic of augmeetee algorithms. E.g., in the paper warm saam-itatting max- flow by Davies al. (2023) most of the technical insights are in the part of the algorithm that projects any (potentially infeasible) prediction into feasible solution.
I 'Our source code is available at gi thub. com/ a dammoo att.aattttttteteeaaaaaaeaaaee
4

---

Published as a conference paper at ICLR 2025
Even when the imput changes very slightly, previously feasible solution may not be feasible anymore, so one should not expect feasibility of predictions based on past data. One such example scenario is given in our experiments the Steiner Tree problem in the full version of the paper (Antoniadis et al., 2024), where the underlying graph is fixed and the set of terminals changes, hence changing the set of feasible solutions. It might be the case that part of the solution is recurring while the other part is changing constantl, from instance to instance. Then, a learning algorithm can easily predict the stable part of the solution, but in advance it hard to extend such a partial solution into a complete feasible solution with reasonable accuracy.
1.4 RELATED WORK
Learning-augmenteed approximation algorithms. Approximation algorithms with predictions have far received very little attention and have only been investigated for specific problems and in restricted settings.
Bampis et al. (2024) studied dense variants of several hard problems such as Max Cut, Max S-SAT, or k-Densest Subgraph - which all are examples of maximization selection problems'. In the dense setting, these problems admit polynomial-time approximation schemes. In particular, for any fixed e <> 0, there is a (1 - --aaproxximation algorithm for Max Cut by Arora et al. (1999) that runs in time O(n1/e), i.e. exponential in the precision parameter 1/e. Bampis al. (2024) propose an algorithm that always runs in time (113.5) and achieves approximation ratio depending on the quality of the received prediction. An interesting feature of their work is that the algorithms in the dense setting need only a small sample of the predicted solution to achieve their guarantees. In particular, they only need to know (polyylog n)) bits of information about items belonging or not belonging to the optimal solution to achieve approximation ratio of the form - [(1), where denotes the prediction error.
Ergun et al. (2022) and Gamlath et al. (2022) independently proposed linear time algorithm for k-Means Clustering that receives labels of the input points as predictions. This problem can be formulated as a minimization selection problem only in the special case where the number of potential centers is bounded (e.g., if the potential centers are the input points themselves). If the prediction has per-cluster label error rate at most a with respect to some (1 -pprroxiiatee solution, their algorithm achieves an approximation ratio of 1 + O(x). The algorithm uses techniques from robust statistics identify outliers in the predicted labeling. Nguyen al. (2023) slightly improve upon this guarantee in their follow-up work.
There are also two very recent works, on the Max Cut (Cohen-Addad et al., 2024) and Independent Set (Braverman et al., 2024) problems, in the setting with e-accurate predictions. In this setting, each input item comes with a label (indicating whether the item belongs to fixed optimal solution or not), which is correct with probability 1/2 + independently from other labels. The two papers show how to breach the respective approximation ratio barriers of 0.878 and n² 11)((1), for any e O. Note that our results assume that the incorrect parts of the prediction are selected adversarially rather than randomly.
Other learning-augmenteed algorithms. Another related line of work is that on exact offline algorithms with warm start. In this setting, the algorithm, in contrast to starting its computation from scratch, has access to predictions or information (e.g., partial solution) that allow it to start computing from a "more advanced" state, leading to an improvement in the running time, Such results include Kraska et al. (2018) on binary search, Dinitz et al. (2021): Chen et al. (2022) on Bipartite Matching, Feijen and Schäfer (2021); Lattanzi et al. (2023) on Shortest Path, Polak and Zub (2024); Davies et al. (2023) on Max Flow, and Bai and Coester (2023) on Sorting. There are also works considering multiple predictions (Dinitz et al., 2022; Sakaue and Oki, 2022) and a work by Tang et al. (2020) on using reinforcement learning to improve the cutting plane heuristic for Integer Programming.
Since the seminal papers by Kraska et al. (2018) and Lykouris and Vassilvitskii (2021), which initiated the study of learning-augmented algorithms in the modern sense, many online computational problems were considered. There are papers on, e.g., ski rental (Purohit et al., 2018), secretary problem (Dütting et al., 2024), energy efficient scheduling (Bamas al., 2020), online page migration
'F.g. for Max Cut, X' C 2 contains all sets of edges that correspond cut in the input graph.
5

---

Published as a conference paper at ICLR 2025
(Indyk et al., 2022), online TSP (Bernardini al., 2022), and flow-time scheduling (Azar et al., 2021; 2022). Further related works can be found on the website by Lindermayr and Megow (2022).
MINIMIZATION PROBLEMS
Our algorithm for minimization selection problems with linear objective receives a prediction X [n] which may not be feasible. It changes the weight of each item in to 0 and runs a conventional p-approximation algorithm on the problem with those modified weights. This way, we obtain solution which is always feasible and its quality is described by the following theorem. In the full version of the paper (Antoniadis et al., 2024), we show that this simple approach already matches lower bound based on the UGC.
Theorem 1. Let II be mininization selection problem, and let A be p-approximation algoritlum for IT running in time T(n). Then, there exists an ((T(n))-tim
caaming-augmented approximation algorithm for II with the following guarantee: Upon receiving (not necessarily feasible) predicted
solution X S [nl], outputs a solution X such that, for any feasible solution X' E X, we have
(XX E w (X') + n + 1) -1.)) 1T, where (17* ,n ) is the error of X with respect to X'.
We remark that if X = X is an optimal solution with objective value OPT, the preceding bound implies that our algorithm's 's approximation ratio is at most
1 + (p 17
OPT
Proof. The algorithm works as follows: Set
0,
i X
w(1)
for = 1n
(()),
otherwise
Run algorithm A with weight function w and return X, the solution returned by the algorithm.
We claim that w(X)= > wxX') + 17* + (p- - 1)m_ Since A is a p-approximation algorithm and X" is a feasible solution for Wi, ... W/, it holds that
w (X] \ X)= = xX) < p. wx) = p. w(X 8).
Then,
w(X) w(Xn + w(X x | (P)
< <w(Xn8)+ + p. w(X' 18)
(
w())) (2))
(0- ( 18).
Note that
w(X) + w(X' | () = ( = w(X) + w(x (x).
Thus we have,
w(X) < W (XX) + w(8 \ x') + (p - 1) w(X') 18) = w(x' + + + (p - 1)m7,
where (11 m))) ) the error of X with respect to X X' = =x is an optimal solution, we have
w(X)= < OPT+*7' n + (p 17 1 + n- + (p 1) "7) OPT.
OPT
In principle, the false-positive prediction error can be unbounded in terms of OPT, and therefore the approximation ratio of the algorithm of Theorem 3 cannot be bounded by any constant. That is, using the terminology of cearning-augmenter algorithms, the algorithm is not robust. However, as is the case for any offline algorithm. it can be robustified without increasing the asymptotic running time by simply running A in parallel and returning the better of the two solutions.
Corollary 2. Under the same assumptions as in Theorem 1 there exists a learning augmented algorithm for II running in time ((T(n)) with approximation ratio
n + (p- 1). 17
min
OPT

---

Published as a conference paper at ICLR 2025
2.1 EXAMPLE APPLICATIONS
Minimum (and Min- Weight) Vertex Cover. In an undirected graph G = E), ) a vertex cover is a set X S V such that every edge e = (u, v) E E has u E X or v E X. The Min- Bin-Weightt Vertex Cover problem asks, given graph G = (V, E) with vertex weights w V + Rgg, to find a vertex cover X S V of the minimum total weight wxX)) and the Minimum Vertex Cover problem is the special case with unit weights Veev w(u)= = 1, i..., asks for vertex cover of minimum cardinality.
Already the unweighted variant is a very hard problem: Minimum Vertex Cover is included in Karp's seminal list of 21 NP-hard problems (Karp, 1972). Furthermore, under the UGC it NP- hard to approximate Minimum Vertex Cover with any better than 2 multiplicative factor (Khot and Regev, 2008). This lower bound matches a folklore 2-approximation algorithm, which runs in linear time. Yehuda and Even (1981) show that also Min-Weigh Vertex Cover admits a linear-time 2- approximation. Therefore, we can directly apply Theorem I and get a linear-time algorithm for Min- Weight Vertex Cover with the approximation ratio 1 (17* + + + )/OPT.
Minimum (and Min- Wiinhh Steiner Tree. Given an undirected graph G = (V, E) and a subset T S V of the vertices referred to as terminals, the Minimum Steiner Tree problem asks for a set of edges X C E of minimum cardinality such that all terminals in T belong to the same connected component of (V, X). In the Min- Biight Steiner Tree problem the input also contains edge weights w: E R 20 and the goal is to find such set X minimizing the total weight w(X).
Minimum Steiner Tree is also among Karp's s 21 NP-hard problems (Karp, 1972). A folklore algorithm, the so-called minimum spanning tree heuristic yields 2-approximation algorithm, also for the Min- Weight Steiner Tree problem, and Mehlhorn (1988) shows how to implement it in (near-)linear time O(EE + log IV].. A long line of work contributed many (polynomial- -immmeell-eme) better-than- 2- 2-approximation algorithmss, with the current best approximation factor 1.39 given by Byrka et al. (2013), but none of these algorithms runs in (near-)linear time and for many of them the running time is an unspecified polynomial with huge exponent. The inapproximability lower bound is 96/95 (Chlebík and Chiebíková, 2008), leaving a big gap open.
Our Theorem 1 together with Mehlhorn's algorithm gives linear time dearning-augmentte Min- Weight Steiner Tree algorithm with approximation factor 1 + (1) + v //OPT. For sufficiently accurate predictions, it gives better and faster approximation than the best conventional algorithms. In Section 4 we show how to exploit specific structural properties of the problem in order to obtain an even better algorithm.
Min- Meinht Perfect Matching. For an undirected graph G = (V, E) with edge weights w : E Ryo the Wii-he Perfect Matching problem asks to find set X C E of exactly = |V|/2 edges such that each vertex u E V is an endpoint of exactly one of these edges and their total weight w(X) is minimized. Unlike the previous two examples, this problem belongs to the class P and optimal solutions can be found with a fairly complicated exact algorithm that runs in ((V] time (Edmonds, 1965; Gabow, 1990). For the special case of edge weights satisfying the triangle inequality Goemans and Williamson (1995) give a linear-time 2-approximation algorithm. It is an open problem whether special case. We show how to achieve it assuming sufficiently accurate predictions.
faster than D([V][E)) is possible for this
This time we need to work more than in the previous two examples. That is because the problem we tackle is not a selection problem- - because of the triangle inequality not every weight function constitutes a correct input. If we tried to apply Theorem directly we would run into the issue that decreasing the weights of predicted edges to zero may violate the triangle inequality.
Let us start by defining the so-called V V-join problem: Given an edge weighted graph find a min- weight set of edges that has odd degree on all the vertices of V. Goemans and Williamson (1995) give a 2-approximation algorithm for the V-join problem. They also show how to short-cut p- approximate solution to the V-join problem to get p-approximate solution to the Min-Weight Perfect Matching, provided that the edge weights satisfy the triangle incquality. Their algorithm runs in near- linear time.
"This special case is subproblem in the famous 1.S-approximation TSP algorithm by Christofides (2022).
7

---

Published as a conference paper at ICLR 2025
Our Barriing-augment algorithm for Min-Weei Weight Perfect Matching works in two steps. First, it uses Theorem with the algorithm of Goemans and Williamson (1995) to find solution to the V-join problem with approximation ratio at most 1+ (ny + n //OPTT Then, provided that the original graph satisfies the triangle inequality, it transforms the V-join solution into a perfect matching with the same approximation ratio, using the short-cutting procedure of Goemans and Williamson (1995).
3 MAXIMIZATION PROBLEMS
Our algorithm for maximization selection problems with linear objectíve receives a prediction X [ni] which may not be feasible. It changes the weight of each item in [n]] X to 0 and runs the p-approximation algorithm for the complementary problem to find set Y. This way, it obtains solution X [n] Y that guaranteed be feasible. Its quality is given by the following theorem. In the full version of the paper (Antoniadis et al., 2024) we show that this simple approach already matches lower bound based on UGC.
Theorem 3. Let be some maximization selection problem. Let A be T (nn)-time p-approximation algorithu for the following complementary problem: Find subset of items Y C [nn] minimizing w(Y) approximation
such that ([n] \ Y) E X. Then, there exists an ((T(n)) time
algorithm for 11 with the following performance. Receiving (not necessarily feasible) predicted
solution X [nl], outputs a solution X such that, for any feasible solution X' X, we have w(X)= 3 w(X)
(p - 1)n -7, where (1²*,1") is the error of X with respect to X'.
If = X is an optimal solution with objective value OPT, the preceding bound implies that our algorithm's 's approximation ratio is at most
1)-nt* +
OPT
Proof. The algorithm works as follows: Set
(i),, if x
((1)
for E [n].
0,
otherwise
Run algorithm A with weight function T and let denote the solution returned by the algorithm. Return X [r]] Y.
By the definition of the complementary problem, we have that X = [^] Y E X' is a feasible solution I1. It remains to lower bound the weight of that solution in terms of w(X).. Note that
w(X)= = w(X) w(X \ XX) w(X' ()
Moreover, [n] \ X' is feasible solution to the complementary problem with weights w. because X' X. Hence, since A is a p-approximation algorithm, we get
w(Y) & p- i ((x) \ X') p. w X').
Finally, we have
w(X) = w[[n] (1) > w(x) w(Y
w(X) w( X') w(X' | 8) pro(A X') w (X') (p- 1)n 17
where (n) ,m)) is the error of X with respect to X'. If is an optimal solution, we have
(p 1) n7 + ОPP.
w(X) OPT (p 1)n
OPT
Similarly to Theorem 1, the algorithm implied by Theorem 3 can be robustified by running it in parallel with conventional approximation algorithm A' for problem II.
Corollary 4. Under the same assumptions as in Theorem 3 there exists a learning augmented algorithm for TI running in time O(T(n)) with approximation ratio
1 1- (p 1)n +
max
OPT
where pl is the approximation ratio of the best known algorithm for IT running in time O(T(n)).
8

---

Published as a conference paper at ICLR 2025
3.1 EXAMPLE APPLICATIONS
Maximum (and Max- Weight) Clique (and Independent Set). Given an undirected graph G' = (V, E), an independent set (also called stable set) is a subset of vertices X S such that no two vertices in X share an edge. The Maximum Independent Set problem asks for an independent set of largest cardinality. In the Max- -eighttttt Independent Set problem the input also includes vertex weights V 1g and the goal is to find an independent set X maximizing the total weight w(X). In the complement graph G¹ = ( V, (%) E)), these problems are equivalent to the Maximum (and Max- fax-Weight) Clique problems, which ask for the largest cardinality (weight) complete subgraph Kg C.
Maximum Clique (and Independent Set) is not only NP-hard to solve exactly (Karp, 1972), but it is also NP-hard to approximate within any factor better than n 1-c for any e > 0 (Hästad, 1999). Quite conveniently for us, the complementary problem to Max- Max-Weight Independent Set is Min- Min-Weight Vertex Cover, which can be --approximated in linear time (Bar- YBhuuYa and Even, 1981). Thus, applying Theorem we get linear-time leaming-augmmntee algorithm for Min-Weigh, Independent Set (and Clique) with approximation ratio 1 - (n) 77 //OPT, which is in striking contrast to the aforementioned impossibility of any nontrivial approximation ratio for conventional algorithms.
Knapsack. Given the knapsack capacity e and n items, the i-th of which has size s; and is worth wis the Knapsack problem asks to find a subset of items of total size at most c that maximizes the total worth. Knapsack another example from Karp's 's list of NP-hard problems (Karp, 1972), but admits approximation schemes. In particular, it can be approximated to within factor (1 e)) in time Ö(n + E 3) (Chen et al., 2024; Mao, 2024). Unfortunately. these asymptotically optimal algorithms based structural results from additive combinatorics that make the constants hidden in the asymptotic notation enormous and render the algorithms themselves impractical. Perhaps a more practical approach is the On log(e-1) + c- (22.5) 2.5m-time algorithm by Chan (2018). Still, if our goal is to solve with high accuracy (i.e., small <) many similar Knapsack instances, it might be a useful strategy use Chan's 's algorithm only on a small fraction of those instances, learn from the obtained solutions a predicted solution, and feed it to a much faster solve the remaining majority of instances.
algorithm in order to
In the following lemma (proved in the full version of the paper (Antoniadis et al., 2024)) we show that the problem complementary to Knapsack admits an On log ri)-time 2-approximation algorithm. Theorem 3 then implies the existence of an O(n log n)-time Baaning--augentee algorithm for Knapsack with approximation ratio (1) + rj //PT.
Lemma 1. There an Onn log n)- 2- 2-approximation algorithm for the following problem: Given items, the i-th of which has size s; and is worth w,, and the target f, find a subset of items of total size at least t that minimizes the total worth.
4 REFINED BOUNDS FOR STEINER TREE
We describe refined algorithm for Steiner Tree based on 2-approximation algorithm by Mchlhorn (1988). Our careful analysis describes how it detects and avoids false positives with high weight. Our algorithm uses a parameter > 1 to adapt its treatment of the prediction. With copies Mehlhorn's 's algorithm, and a approaching infinity corresponds to the algorithm in Theorem 1. However, a different choice of may give better results. We illustrate this by an example and show how to achieve performance close to the best choice of a with only a constant factor increase in running time in the full version of the paper (Antoniadis et al., 2024).
its behavior
The algorithm receives as input graph G = (V, E). set T C V of k terminals, a weight function w: : E + R20, and a set X C E of predicted edges. First, scales down the weight of edges in X by dividing them by the parameter a. Then, it uses the algorithm of Mehlhorn (1988) to compute a minimum spanning tree MST,, of the metric closure of the terminals with respect to the scaled edge weights. In the end, the algorithm outputs the union of edges contained in paths corresponding to the connections in MST., The algorithm is summarized Algorithm 1.
Proposition (Mehlhorn (1988)). The minimum spanning tree of the metric closure (T; (b)) of the graph G can be computed in time near- eaar-innerraaaa in the size of G.

---

Published as a conference paper at ICLR 2025
Algorithm 1: Steiner tree with predictions
Parameter: a 3 1;
foreach E E: do
e X then (c(e) := w(e)/a;
else Wa (e) == w(e);
Compute MST, of the metric closure G = (T, (2) of G with weights wa using Proposition 1;
=0
foreach edge = {2) in MST do
Choose p(e) C E the cheapest path in G from & l2 with respect wai
: X p(ee);
return X;
4.1 ANALYSIS
Recall that G = (V, E) denotes the imput graph, and let G = (T, (22) denote the complete graph on the terminals 7 C V. For any weight function w E - I8 zu. consider the shortest path metric on terminals induced by w, i... for an edge e in G between f1 and t2, its cost c(e) is equal to the length of the shortest path p(e), with respect to w, from t to t2 in G. There is natural correspondence between an edge e (the cost c(e)) in G and the set of edges p(e) S E in G (weight w(p(e))). Let MST denote minimum spanning bound.
G. Our algorithm satisfies the following performance
Theorem S. Consider graph G = (V, E) with edge weights w: E - - and a set T C V of terminals. Let X' _ be any Steiner tree on G and be a set of min 1,, X'I edges with the highest cost contained in MST. Our refined algorithm outputs a Steiner tree X of total weight
w(X) (1+ w(x') xx(x)(()) + (1- (1-2)
min { (a Σd(el
n
(I)
where (11 (,)", is the prediction error of X with respect to X'
With X' XX being an optimal solution of cost OPT and a = 1, the bound in (1) is equal to 20PT, which corresponds to the conventional algorithm which ignores the predictions. With a approaching infimity, its limit is OPT + + better than both in case of X X" containing a small number of edges of very high weight. Compared to Theorem 1, + in (1) is capped by (a - 11) Ees c(e) where E.es c(e) < c(MST) < 2w(X") since Mehlhorn's algorithm is 2-approximation algorithm for Minimum Steiner Tree. Since we always have ') < ww((' ve(X*), (1) shows that Algorithm is 2c-approximation algorithm regardless of the prediction error.
matching the result from Theorem 1. However, it can be much
We defer the rest of the analysis the full version of the paper (Antoniadis et al., 2024).
DISCUSSION
We initiated the study of algorithms with predictions with a focus on improving over the approximation guarantees of classic algorithms without increasing the running time. This paper focused on the wide and important class of selection problems, but it would be interesting to investigate whether similar results can be obtained for central combinatorial optimization problems that do not belong to this class, c.g., clustering and scheduling problems problems with non-linear (e.g.. submodular) objectives.
We demonstrated, with the example of the Steiner Tree problem, that refined algorithms with improved guarantees are possible for specific problems. A second, implicit, advantage of our refined Steiner Tree algorithm is that its actual performance could be bounded in terms of quantity directly related to the optimal cost, thus avoiding the additional robustification step. An interesting direction for further research would be identify other problems satisfying these two properties.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Marek Eliáš and Moritz Venzin were supported by the European Union NextGenerationEU, in the framework of the FAIR Future Artificial Intelligence Research project (FAIR PE00000013 CUP B43C22000800006), The views and opinions expressed are solely those of the authors and do not necessarily reflect those of the European Union, nor can the European Union be held responsible for them.
REFERENCES
Sungsoo Ahn, Younggyo Sco, and Jinwoo Shin. Learning what to defer for maximum independent sets. In Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 134-144. PMLR, 13-18 Jul 2020. URL https::/proceeteee
mll press v119/ awwaaahn2aaa.. html.
Antonios Antoniadis, Marek Eliás, Adam Polak, and Moritz Venzin. Approximation algo- rithms for combinatorial optimization with predictions. CoRR, 1os/2411.16660 2024. doi: 10. 48550/555AAA ARXIV. 2411 2411.16600. 16600.
Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci., 58(1):193-210, 1999, doi: 10. 10.1006/JCSS 1998. 605. Announced at STOC 1995.
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1070-1080. ACM, 2021. doi: 10 15411/5// 34033330333322 3451225..45122 023.....
Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for minimizing flow time. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 252-274. SIAM, 2022. doi: 10 10.113711.97816119999
Xingjian Bai and Christian Coester. Sorting with predictions. In Advances Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurIPS 2023, 2023. URL http: http::/ppapppseee nips htsppppseecpppperteeeeeeeeeee html.
Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning aug- mented energy minimization via speed scaling. In Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, 2020. URL URLattpss:/prooeeiiie www.riiiiiiinnnnnnnoeeeeeeee.eee nwwrips..p.... ctt.cc//pppaa/ee http//ppee/222///2222 0tt.://0e33005111-------ttrteete matsstract.hml......
Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Parsimonious learning-augmented ap- proximations for dense instances of NP-hard problems. CoRR, abs/2402.02062, 2024. doi 10. 188500/ARXII 22200
Reuven Bar-Ya Ychuda and Shimon Even. the weighted vertex cover problem. 10 10.1016/0196-6772 (B1) 90020-1.
A lincar-time approximation algorithm for
J. Algorithms, 2(2):198-203, 1981. doi:
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological d' d'horizon. European Journal of Operational Research, 490(23:405-421, 2021. ISSN 0377-2217. doi: https: htt//ooooorggg// www.ooo...............oooo/..... 1016
1tt.:/..1111............ j.r.jrr.jjjr.r.//o 2020. 07 063.
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaaccmella Nicole Megow, Leen Stougie, and Michelle Sweering. A universal error measure for input predictions ap- plied to online graph problems. In Advances in Neural Information Processing Sys- tems 35: Annual Conference Neural Information Processing Systems 2022, NeurIPS 2022, 2022. URL http:://pppeeee nips de faarrrffieee/pee st/ppppperfille/ppppee//// 1521 2bd (32322554443abboe 2bbd226544sabbbbccclll1 98w.llb999222633113
hash// htt.eaaeeeeaacceeeooooooeeeeeeen Castrsrat------aeeeeeeeee html.

---

Published as a conference paper at ICLR 2025
Edouard Bonnet and Florian Sikora. The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration. 13th International Symposium on Parameterized and Exact Computation. IPEC 2018, volume 115 of LIPlcs, pages 26:1-26:15.. Schloss Dagstuhl- Leeinniz-Zentrum für Informatik, 2018. doi: 10.4230/15 LIPICS. IPEC. 2018 8. 26. https: (rpacechallenge..oo 2018/ ser-teee
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Searning-augment maximum independent set. Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques, 2024. URL www.ttttt//// http:://xxiivvrro
240.. 113644
Jaroslaw Byrka, Fabrizio Grandoni, Thomas RothvoB, and Laura Sanità. Steiner tree ap- proximation via iterative randomized rounding. J. ACM, 60(1);6:116::) 2013. doi: 10. 10.1145/2432622 22124442222224322255 2432628.
Timothy M. Chan. Approximation schemes for 0-1 knapsack. In Ist Symposium Simplicity in Algorithms, SOSA 2018, volume of OASIcs, pages 5:1-5:12. Schloss Dagstuhl Leiibniz- Zentrum für Informatik, 2018. doi: 10. 4230/23300TT/ /OA.IICSS.....//.. SOSA. 2018.5
Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. International Conference on Machine Learning, ICMI. 2022, volume 162 of Proceedings of Machine Learning Research, pages 3583-3602. PMLR, 2022. URL ht httpps:// http:///ppcceeeeeeeeemee mlr wawl.ppres//ee /v1 62/ chen22v htmll.
Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. A nearly quadratic-time FPTAS for knapsack. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, STOC 2024, pages 283-294. ACM, 2024. doi: 10.1145/ 00.1145533688261 .1122660664444 3649730.
Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci., 406(3):207-214, 2008. doi: 10. 10.1066 6/J. TCS.
046.
Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Announced as technical
Res. Forum, 3(1), 2022. doi: 10. 1001 0000544030--000000 report in 1976.
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Pani- grahi. -ungeneed approximation algorithms for maximum cut and related problems. In Proceedings of NeurlPS 2024 (in press), 2024. doi: 10. 118550/ARIVV 2402 240.218262 18263.
George B. Dantzig. Discrete-variable extremum problems. Operations Research, 5(2):266-288, 1957. doi: 10.1287 pp..
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster Ford-Fulkerson. In International Conference on Machine Learning, ICML 2023, volume 202 of Proceedings of Machine Learning Research, pages 7231-7248. PMLR, 2023. URL https: / //proceedings... mlr .er.sppresss.. v202/
wttpe////222//avve222bbb dwv.es23........oo/ html.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, pages 10393-10406, 2021. URL httpt::://ppoooceeeeee www.inngnnnn.nsneeeeeeeeeeerun neurips..p...em www..pp.cccpppper/20000.. /ash// 561
attpa//ee...7776.--aaaaaa....... Abstract.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. In Advances in Neural Information Processing Sys- tems 35: Anmual Conference on Neural Information Processing Systems 2022, NewrIPS 2022, 2022. URL http::/papers. nips oc wwtpppppppppeiiieeeee httpeeeeeeiieeeeeee/////00 /ashh/ html.
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. Math. Oper. Res., 49(2):85-887, 2024. doi: 10. 1287 00287/MOOR..0 2023. .3824.11144, Announced at EC 2021.
Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. of Res. the Nat. Bureau of Standards, 69 1:125-130, 1965.
12

---

Published as a conference paper at ICLR 2025
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented k-means clustering. In The Tenth International Conference on Learning Representa- tions, ICLR 2022. OpenReview.net, 2022. URL https: http///pppp/eeeeeeeeeeeeeeeeeeet net wttp://wwee/tttmtitiiiimm forummidd X8CITHHxYYY.
/
Willem Feijen and Guido Schäfer. Using machine learning predictions to speed-up Dijkstra's shortest path algorithm. CoRR, abs/2112.11927,, 2021. URL https://arxiv.oor 2112. 927.
Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the First Annual ACM- SIAM Symposhum on Discrete Algorithms, pages 434 443. SIAM, 1990. URL http: /dl. am. org/ ci ton. c fm? 0 3222011..3202
Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, volume 178 Proceedings of Machine Learning Research, pages 1463-1509. PMLR, 2022. URL https: httpss//pocceeddeeeee mlr.presse v178///// gam aamlath22a html.
Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. do1:
10. 0011117//009753999222222
Announced SODA 1992.
Johan Hästad. Clique is hard to approximate within n 1-epsilon Acta Mathematica, 182(1):105-142, 1999. doi: 10.1007/BB BB0007/FFO2330 /BT////F22222552 Announced at FOCS 1996.
Piotr Indyk, Frederik Mallmann- Trenn, Slobodan Mitrovic, and Ronitt Rubinfeld. Online page migration with ML advice. International Conference on Artificial Intelligence and Staristics, AISTATS 2022, volume 151 of Proceedings of Machine Leurning Research, pages 1655-1670. PMLR, 2022. URL https:ttp//.o http:///rrpooccnnno....eeeeeeae/
ml wwt.s/pwwsswweeeeeeeee.
html.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem, 2019. URL httphtt/////t//..orr///////// 01227.
Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. doi: 10. 1 1007 978 484 684-2001-2_9
Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J.
Comput. Syst. Sci., 74(3):335-344 349, 2008, doi: 10111166611 6 20025.2200... 019.
Lawrence T. Kou, George Markowsky, and Leonard Berman. A fast algorithm for Steiner trees. Acta Informatica, 15:141-145, 1981. doi: 10. 100.000/00000 /BF.0080002.......
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings the 2018 International Conference on Management of Data, SIGMOD Conference 2018, pages
ACM, 2018. doi: 10. 10.1145/ 31833188133111111 31969099.
Silvio Lattanzi, Ola Svensson, and Sergei Vassilvitskii. Speeding up Bellman Ford via minimum violation permutations. In International Conference on Machine Learning, ICML 2023, volume 202 of Proceedings of Machine Learning Research, pages 18584-18598, PMLR, 2023. URL https: https////ccceeeieeseee wall..resss v202/22222//////// 22302/1ate lattanzi23a html.
Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https:// wotoriitmsswwth--peeeeee ions github. io, 2022. Accessed 22 May 2024.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J.
ACM, 68(4):24:1124:22 2021. doi: 10. 001144/344579 Announced at ICMI. 2018.
Xiao Mao. (1 e) alaappooxinttion of knapsack in nearly quadratic time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 295-306. ACM, 2024, doi: 10. 11 45 61 8260. 266.666.6.666666666..
13

---

Published as a conference paper at ICLR 2025
Kurt Mchlhomn A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3):125-123 128-128, 1988. doi: 10. N0.1016/002C-00 (88) 90066-X.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020. doi: N0.1017/9781108 978110862 63 4344 037.
Thy Dinh Nguyen, Anamay Chaturvedi, and Huy L.. Nguyen. Improved learning- augmented al- gorithms for k-means and k-medians clustering. In The Eleventh International Conference on Learning Representations, ICLR 2023. OpenReview.net, 2023. URL httt:::://pperreiieee
net/forun dd=ddsFiiiii id=dcsFiAl_oo.
Adam Polak and Maksym Zub. 186:106487, 2024. ISSN 0020-0190. doi: 10 1ww.11011..ppp 2024 .106487.
maximum flow. Information Processing Letters,
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: An- nual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages (684-9692) 2018. URL 13a427badebe0e
meureiiip pccppape///0////////ccp aat22008haas /hash/ Abstract html.
Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin Enrique Villalobos López, and Carlos Segura González. Source code of the CIMAT solver for the Steiner tree problem.
https: / /ighhu.. htmm/HeathhlifffAC www.fa///eeeeeeeeeeeeeeeee wwweeeeeeeeereereeeeeeer 2018. Accessed 22
May 2024.
Shinsaku Sakaue and Taihei Oki. Dissrete-oonve--malyi-------s framework for warm- starting algorithms with predictions. In Advances in Neural Information Processing Sys- tems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022. URL http: htttp://papers wwwpeaapppeeeeeeeaeeeeeeee nips. httppprrrllllepppprrr/ee/e 2t////2222/hhh//// /hash/ html.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 9367-9376. PMLR, 2020. URL pestp://proceeeee
ml www.gngwww.....................e /vll 9 9/tang200 0a html.
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978- 978-0-521-19527-00
14


Reviews:
[{"review_id": "mAV1B3CsOu", "reviewer": "Reviewer_DLoK", "summary": "This work falls under the he newly evolving area of learning-augmented algorithms.  Consider an optimization problem of the form:  There are $n$ items with weights $w_1, w_2, \\cdost w_n$. Given a (implicit) collection of subsets of $[n]$ find a subset whose weight is minimized/maximized. Suppose that we are given a prediction $\\cap{X}$ for the optimal solution. Can the algorithm exploit this additional data and design algorithms with better approximation ratio?\n\nThis work studies the above question and proves that depending on how close $\\cap{X}$ is to the optimal solution (closeness measured in terms of false positives and false negatives), we can obtain algorithms with improved approximation ratio.", "questions": "1. What if predictions come in the form of probabilities/confidences? For each item  $i$, a confidence value $\\alpha_i$, representing the confidence that item $i$ is in the optimal solution set.  How does this model compare to the current work?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem studied is very interesting, natural, and timely\n2. The solution presented is very intuitive and the proofs are easy to follow (this should be taken as negative).\n3. For the general setting, the bounds obtained are optimal.", "weaknesses": "1. The paper is a bit too verbose with many unnecessary details.   For example, detailed discussed of example applications in sections 2.1 and 3.1 is not needed, as these problems fit into the framework in a straightforward manner.\n\n2. I do not know much about the learning-augmented algorithms. So, I am not able evaluate the novelty of the proofs of the present work (this perhaps is the reviewer's weakness, not the paper's weakness). However, a more detailed description of various other models to represent predictions and the algorithmic techniques places this work in context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AR9Xb3msb7", "reviewer": "Reviewer_s3yv", "summary": "The paper provides a generic transformation of worst-case approximation algorithms to approximation equipped with machine learnt advice. The general setting is that of positively weighted selection problems that are subject to combinatorial constraints (e.g., vertex cover, Steiner tree, weighted machine, knapsack, etc). The main result is that given a nearly correct (yet perhaps unfeasible) solution to the optimization problem, one can derive an approximation guarantee close to 1, using as a black box any approximation algorithm for the problem (in particular, a very efficient one). The idea is very simple. For minimization problems, replace the weights of the elements in the advised solution by 0, then run the approximation algorithm on the modified instance. An analogous solution works for maximization problems.\n\nThey also show that under the unique games conjecture, the result is optimal for some problems (e.g., vertex cover). For Steiner tree, they give a better algorithm that is a slight variation of the above general method: instead of zeroing the weight of the advised elements, damp the weights by some factor.\n\nFinally, they provide some empirical evaluation of their methods, on a known benchmark. It's hard to judge the meaning, because it's not clear that this benchmark was design to challenge machine learning approaches, so possibly it is easy to learn and thus overfit the above approach to the dataset (which is quite small; 199 examples).", "questions": "None.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I like the generality of the approach, and its simplicity makes it practically appealing.", "weaknesses": "It's restricted to selection problems, so, for instance irrelevant to partition problems such as clustering. Also, it requires an approximation algorithm for the weighted case, even if the optimization problem that needs to be solved is unweighted. By exploring the combinatorial structure of the problem, one might derive better solutions (as demonstrated for Steiner tree).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j3DLe09yET", "reviewer": "Reviewer_iRrN", "summary": "The paper explores learning-augmented approximation algorithm design for a general selection problem. In this problem, we are given a set of ground elements, each with a non-negative weight, along with an implicit collection of all feasible subsets of these elements. The objective is to select a feasible subset that minimizes or maximizes the total weight.\n\nThe authors focus on the setting where the algorithm can access an (imperfect) prediction of an optimal solution and propose a general framework for integrating classic approximation algorithms with this prediction. For the minimization model, the framework achieves an approximation ratio of $1+(\\eta^+ + (\\rho-1)\\eta^-)/ OPT$, where $(\\eta^+,\\eta^-)$ are prediction errors, $\\rho$ is the classic approximation and $OPT$ is the optimal objective value.  For maximization problems, the framework yields an approximation ratio of $ 1- ((\\rho-1)\\eta^++\\eta^- )/OPT$. The authors apply this framework to several concrete applications. In particular, for the Steiner tree problem, they leverage the characteristics of the problem to provide an improved ratio.", "questions": "- See the weakness above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Learning-augmented algorithmic design was originally applied in online optimization to leverage learning in order to address uncertainty. This paper extends this approach to offline approximation algorithm design, aiming to break through computational complexity—an interesting idea.\n\n- The paper is well-organized. The basic idea is clean and easy to follow.", "weaknesses": "- Although the model is novel, the proposed learning-augmented framework seems quite natural, and the analysis is technically simple. One shortcoming of the framework is that when the given prediction is the whole element set, $\\eta^- =0 $, while $\\eta^+$ can become infinitely large, leading to an infinite approximation (if the robust operation in the corollary is not used). This is a little weird. Could this be fixed by adding a step in the framework to apply classic approximation algorithms to the predicted subset of elements if it is infeasible?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1pfa73vpST", "reviewer": "Reviewer_9d1z", "summary": "The paper is about learning-augmented approximation algorithms for combinatorial set selection problems. More specifically, the authors consider the (abstract) problem of selecting a set of elements of a universe of minimum total weight such that the selected set is feasible. A classic example of such a problem is the Vertex Cover problem. An approximation algorithm runs in polynomial time and computes a solution that is within an $\\alpha$ factor of an optimal objective value. This factor is called the approximation factor of the algorithm. Typical applications for approximation algorithms are optimization problems that are NP-hard to solve optimally.\nMoreover, for some problems such as Vertex Cover, finding a better-than-2 approximation algorithm would contradict standard complexity assumptions such as the Unique Games Conjecture or $P \\neq NP$.\n\nLearning-augmented algorithms are a recently popular method of beyond worst-case analysis, and are nowadays an established subfield in the intersection of algorithm theory and machine learning. The idea is to give an algorithm access to an additional input - a prediction - and analyze a learning-augmented algorithms performance w.r.t. the quality of this prediction. Only a few works have considered approximation algorithms under this framework so far.\n\nThe present paper considers the prediction model where a predicted solution is given to the algorithm. They present algorithms for the general set selection problem that achieve a near optimal performance for perfect predictions and a smooth degradation w.r.t. the number of false positive and false negatives of the prediction compared to some optimal solution.\nAt the same time, the approximation ratio of the currently best-known approximation algorithm can be achieved by running both algorithms and selecting the better solution.\n\nFurther results include:\n- A similar result for maximization problems\n- An algorithm with a controlable tradeoff between consistency and smoothness\n- Lower bounds w.r.t. the Unique Games Conjecture showing that their algorithms are essentially best-possible.\n- Empirical experiments", "questions": "Questions:\n- L128: Can we conclude from this example that the linear depedence $(\\rho - 1) \\eta^-$ is necessary? As far as I understand, this example only gives lower bounds on the endpoints of the error functions, so in principle one could have a non-linear dependence.\n\n\n\nFurther comments on the writeup:\n- L81: I think it would improve the readability if you explain before that the idea is to predict a solution (= some set).\n- L114: Here I was wondering what happens if there are multiple optimal solutions. Maybe you can add some note here. Later in the theorem, you solved it differently.\n- L317: \"In other words, using the terminology of\" sounds a bit redundant.\n- L327: I think it must be $X \\subseteq V$, because in a graph where all edges are self-loops, we have $X = V$.\n- L361: \"this problem is not known to be NP-hard\" sounds a bit confusing given that it is known to be in $P$.\n- L479: \"it scales the weight [...] by parameter $\\alpha$\" Here I was unsure what this means, i.e., if it is $w/\\alpha$ or $w \\cdot \\alpha$. Of course, it is precise in the algorithm.\n- L525: \"since the Mehlhorn's algorithm is\". I think it is \"since Mehlhorn's algorithm is\".\n- L1000: I would have like a bit more details why Theorem 8 implies that Theorem 1 cannot be improved.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper provides learning-augmented algorithms for various problems as well as general tight lower bounds on these results. The approximation guarantees in the case of good predictions improve over complexity lower bounds in the setting without predictions. \n- There are only few papers on approximation algorithms with predictions. Thus, I have the feeling that its simplicity and strong results have an impact, and these results may be important for future works.\n- The proposed algorithms are simple yet essentially best-possible.\n- The paper is very well written, gives a structured overview of related work, and provides some empirical insights.", "weaknesses": "- One minor weakness is that the results are achieved using quite simple standard techniques. However, given that the analysis is essentially tight, and this is an AI conference and not a TCS conference, I think this is really only a minor issue.\n- Compared to online algorithms with predictions, one can guarantee robustness for approximation algorithms for free by running both algorithms in parallel. Thus, there are no interesting insights between consistency and robustness for approximation algorithms. However, the authors show that similar trade-off are present between consistency and smoothness, give paramterized results and moreover discuss how to choose such parameters. Thus, I think that this is also only a minor weakness.\n- I would have liked a concluding discussion about the impact of these results and a potential outlook at future questions at the end of the paper. This could be addressed in a camera-ready version though.\n- In the \"results\" paragraph of the empirical evaluation, I was missing your takes on how your algorithm compares to CIMAT, given that it is part of your experiments. In general, I would have liked to see a larger discussion here. This could be also easily addressed in a revised version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)