Pith. sign in

REVIEW 2 major objections 5 minor 3 cited by

Approximation Algorithms for Combinatorial Optimization with Predictions

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Zeroing the weights of predicted items lets any approximation algorithm use predictions, with error-dependent guarantees and no slowdown.

desk verdict Clean black-box upper bounds and a solid Steiner Tree analysis, but the class-wide optimality claim rests on a sketched unweighted reduction that needs real proof. read the letter →

arxiv 2411.16600 v1 pith:GL3XNION submitted 2024-11-25 cs.DS cs.LG

Antonios Antoniadis , Marek Eliáš , Adam Polak , Moritz Venzin This is my paper · ORCID
classification cs.DScs.LG MSC 68W2590C2768Q25
keywords learning-augmentedalgorithmsapproximationcombinatorialoptimizationselectionproblemspredictionerrorvertexcoverSteinertreeUniqueGamesConjecture
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a general method: any approximation algorithm for a selection problem—choosing a minimum- or maximum-weight feasible subset of items—can be made prediction-aware with no asymptotic slowdown, as long as it receives a predicted set of items that may be wrong or infeasible. For minimization, setting the weights of predicted items to zero and running the original algorithm on the modified instance gives, from a $\rho$-approximation algorithm, approximation ratio $1 + (\eta^+ + (\rho-1)\eta^-)/\mathrm{OPT}$, where $\eta^+$ and $\eta^-$ are the total weights of false positives and false negatives. Perfect predictions therefore return optimal solutions, and the guarantee degrades continuously as prediction error grows. The paper also shows, under the Unique Games Conjecture, that this dependence on prediction error cannot be improved for the class of selection problems as a whole, and it refines the method for Steiner Tree so that high-weight false positives do not dominate the cost.

What carries the argument

The load-bearing object is the modified-weight instance: for minimization, $\bar{w}(i)=0$ for $i \in \hat{X}$ and $\bar{w}(i)=w(i)$ otherwise; for maximization, $\bar{w}(i)=w(i)$ for $i \in \hat{X}$ and $0$ otherwise. Running any $\rho$-approximation on this perturbed instance is what converts predictions into feasible solutions, and the proof's core identity is $w(\hat{X}) + w(X'\setminus \hat{X}) = w(X') + \eta^+$, which turns the approximation guarantee into the error-dependent bound. The lower-bound argument uses UGC-hard gap instances of Vertex Cover assembled into a disjoint-union gadget $G_0, G_+, G_-$ with scaled vertex weights, so that the normalized errors $\eta^+/\mathrm{OPT}$ and $\eta^-/\mathrm{OPT}$ can be tuned to arbitrary targets $(x,y)$. The refined Steiner Tree algorithm replaces full zeroing by a parameter $\alpha \ge 1$ that scales predicted edge weights down by $1/\alpha$; the analysis charges false-positive edges to the most expensive connections of the minimum spanning tree on the metric closure, with a matroid-exchange pairing of MST edges supplying the cap.

What would settle it

Exhibit a polynomial-time learning-augmented algorithm for Minimum Vertex Cover whose approximation ratio is $1 + f(\eta^+/\mathrm{OPT}, \eta^-/\mathrm{OPT})$ with $f(x,y) < x+y$ for some $x,y \ge 0$, $x+y \le 1$; run it on the three-component gadget $G_0, G_+, G_-$ from the lower-bound proof, where it would have to find a cover of size below $(1-\delta)n$ in the YES case.

Watch

Extended reading notes

Core claim

The central discovery is a weight-subsidy identity. For any minimization selection problem with a $\rho$-approximation algorithm $A$, the paper defines a learning-augmented algorithm that sets $\bar{w}(i)=0$ for every item $i$ in the predicted set $\hat{X}$, leaves all other weights unchanged, runs $A$ on the modified instance, and returns its feasible solution $X$. A direct calculation shows $w(X) \le w(X') + \eta^+ + (\rho-1)\eta^-$ for every feasible $X'$, hence approximation ratio $1 + (\eta^+ + (\rho-1)\eta^-)/\mathrm{OPT}$ against an optimal solution. The maximization analogue sets $\bar{w}(i)=0$ outside the prediction and solves a complementary minimization problem, yielding ratio $1 - ((\rho-1)\eta^+ + \eta^-)/\mathrm{OPT}$. For the whole class these bounds are tight unless the Unique Games Conjecture fails, proved by embedding UGC-hard gap instances of Vertex Cover and Independent Set into the normalized error parameters. A dedicated Steiner Tree algorithm divides predicted edge weights by a parameter $\alpha$ before running the MST heuristic; its analysis caps the damage of false positives by the cost of a small number of MST connections rather than by their full weight.

Load-bearing premise

The optimality of the prediction-error dependence rests on the Unique Games Conjecture; if that conjecture is false, the lower bounds lose their force, though the algorithms' guarantees remain valid.

Editorial extensions

If this is right

  • Every selection problem with a (near-)linear $\rho$-approximation algorithm immediately gets a (near-)linear learning-augmented algorithm; perfect predictions output an optimal solution, and error $\eta$ yields ratio $1 + (\eta^+ + (\rho-1)\eta^-)/\mathrm{OPT}$.
  • For Vertex Cover, Steiner Tree, and metric Min-Weight Perfect Matching, sufficiently accurate predictions beat the known worst-case approximation guarantees while keeping the same running time.
  • For Clique and Independent Set, the maximization construction gives a linear-time ratio $1 - (\eta^+ + \eta^-)/\mathrm{OPT}$, entering a regime where prediction-less algorithms cannot offer any nontrivial guarantee.
  • No learning-augmented algorithm for the whole selection-problem class can improve on the linear dependence on normalized false positives and false negatives unless the Unique Games Conjecture is false.
  • The refined Steiner Tree algorithm, with $\alpha$ searched over a geometric grid, finds a solution within a $(1+\epsilon)$ factor of the best $\alpha$-scaled guarantee in near-linear time, and its experimental evaluation on standard benchmark instances shows near-optimal solutions on predictions with modest error.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The zeroing trick is really a subsidy view of predictions: each predicted item is treated as free, and the algorithm pays only for correcting false negatives and the approximation slack on non-predicted items; this view suggests possible analogues for objectives where the linear decomposition is replaced by a submodular inequality.
  • The paper's PAC-learnability remark implies a practical recipe: on recurring instances with a stable core of optimal-solution items, coordinate-wise majority vote over past solutions supplies predictions that make the near-linear algorithm near-optimal, with the expensive learning amortized across many instances.
  • Because the lower bound rests on UGC, a disproof of the conjecture would leave the algorithms intact but reopen the question of better error dependence for Vertex Cover and Clique; the Steiner Tree refinement already shows that per-problem structure can beat the black-box bound.
  • The $\alpha$-scaling interpolation between ignoring and fully trusting predictions could be exported to other problems built on metric-closure approximation algorithms, provided the approximate solution offers a similar short list of expensive connections to charge false positives against.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper studies approximation algorithms with machine-learned predictions for "selection problems," in which each item has a weight and the goal is to choose a feasible subset minimizing or maximizing total weight. The main upper-bound results are black-box transformations: for minimization, zero out the weights of predicted items and run any ρ-approximation algorithm, obtaining approximation ratio 1 + (η+ + (ρ−1)η−)/OPT; for maximization, a complementary construction gives 1 − ((ρ−1)η+ + η−)/OPT. These are applied to Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Clique, Independent Set, and Knapsack. The paper also presents a refined, α-parameterized algorithm for Steiner Tree with a tight analysis, UGC-based lower bounds for Vertex Cover and Independent Set/Clique asserting that the prediction-error dependence is optimal for the class, and an experimental evaluation on PACE instances with released code.

Significance. If the results are correct, the paper makes a useful conceptual contribution: it shows that a broad class of classic approximation algorithms can be made prediction-augmented without any asymptotic slowdown, with approximation guarantees that degrade smoothly with prediction error. The generic upper bounds (Theorems 2 and 4) are clean, simple, and parameter-free, and the robustified versions are immediate; the refined Steiner Tree analysis in Section 4 is a genuine algorithmic improvement with a matching lower example. The lower bounds are interesting but conditional on UGC and, as detailed below, currently incomplete at the point where the weighted construction is converted to an unweighted instance. I regard the upper-bound half of the paper as solid and the lower-bound half as needing a substantial repair.

major comments (2)
  1. [§5.2, final paragraph of the proof of Theorem 13; also §5.3, final paragraph of the proof of Theorem 14] The unweighted reduction is the load-bearing step for the claimed optimality of the black-box approach, but it is only sketched. The text says: "we take (roughly) 1/x′y′ copies of G0, 1/((1−x′−y′)y′) copies of G+ and 1/((1−x′−y′)x′) copies of G−" and then asserts that any solution achieving ratio 1+x+y−ε must find a cover of size <(1−δ)n in some copy of G+ or G−. No proof is given. The authors must state exact integer copy counts and prove: (i) the normalized prediction errors of the resulting unweighted instance still satisfy η+/OPT ≤ x and η−/OPT ≤ y; (ii) if every copy of G+ and G− has minimum vertex cover size at least (1−δ)n, then the total cost of any feasible vertex cover exceeds (1+x+y−ε)·OPT; and (iii) the boundary cases x=0 or y=0 are handled, since the displayed quotients are undefined there. The rounding of Θ(n) per copy can dominate the ε·OPT slack unless the constants are checked, so "roughly" is not sufficient in a formal lower-bound proof. The same missing argument appears in Theorem 14.
  2. [§5.2 and §5.3, first display of each lower-bound proof] The formula for the optimum value of the weighted instance is written with the unscaled quantities x and y instead of the scaled quantities x′ and y′ defined immediately before. For example, in the proof of Theorem 13 the text states "OPT = (1 − x − y)n/2 + x|X∗| + y|X∗|", but the vertex weights in G+ and G− are x′ and y′. The exact formula should use x′ and y′ in place of x and y. The claim that OPT lies in [(1−δ)n/2, (1+δ)n/2] is true with the scaled quantities, but as written the displayed equality is incorrect. This is repairable, but it must be corrected for the subsequent bounds on η+/OPT and η−/OPT to be formal.
minor comments (5)
  1. [§2, proof of Theorem 2] The sentence "We claim that w(X) ⩾ w(X ′) + η+ + (ρ − 1)η−" has the inequality direction reversed; the proof derives the opposite inequality, which is the intended statement.
  2. [§2, paragraph after Theorem 4] The text says "the false-positive prediction error η+ can be unbounded ... and therefore the approximation ratio of the algorithm of Theorem 4 cannot be bounded by any constant"; this should refer to Theorem 2, since the discussion is about minimization.
  3. [§4.1, proof of Observation 8] The proof states that the weight of the Euler tour with respect to w′α is "2w(X ′) − (1 − 1/α)w(bX ∩ X ′)", but since every edge in bX ∩ X ′ is used twice, the factor 2 is needed: the correct value is 2w(X ′) − 2(1 − 1/α)w(bX ∩ X ′). The statement of Observation 8 already has the factor 2, so this appears to be a typo in the proof line, but it should be corrected.
  4. [§6, "Evaluation metrics"] The normalized cost is printed as (cALPS(α) − cOPT)/(cALPS(α) − cMST); this makes the quantity 0 at the optimum but leaves it undefined when ALPS matches Mehlhorn. The intended formula is presumably (cALPS(α) − cOPT)/(cMST − cOPT), which interpolates between 0 and 1 as described in the text.
  5. [§3 and abstract] The maximization-ratio expression is printed as "1 − (ρ−1) · η+ + η−/OPT", which is ambiguous. It should be typeset with parentheses: 1 − ((ρ−1)η+ + η−)/OPT.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 2 is a direct black-box derivation from the definition of prediction error, and the lower bounds rest on external UGC hardness; the only self-citation is a peripheral PAC-learnability remark.

full rationale

The central upper bound (Theorem 2) is not circular: the algorithm zeroes predicted weights and runs any rho-approximation, and the proof derives w(X) <= w(X') + eta+ + (rho-1)*eta- directly from the definition of (eta+, eta-) and the rho-approximation property. No parameter is fitted to make the theorem true, and the proof does not invoke the result being proved. The example applications and the refined Steiner Tree result (Theorem 7) are likewise derived from explicit charging, matroid-exchange, and approximation arguments; the hyperparameter alpha is not tuned to force the bound, and the guarantee holds for every alpha. The lower bounds in Theorems 13 and 14 are hardness reductions from the external Khot-Regev UGC results, not self-citations; the unweighted gadget in the final paragraph of Theorem 13's proof is asserted rather than fully verified, but that is a completeness and correctness gap, not circularity. The only self-citation is in Section 1.3, where PAC-learnability is justified by citing Polak and Zub (2024, Theorem 5), and Adam Polak is a co-author of the present paper. This is a standard ERM bound used for a peripheral remark about learnability, and it does not support the central optimality or approximation claims of the paper; therefore it does not create a circular derivation. Overall, the paper's derivation chain is self-contained for its main results, and the score of 1 reflects only the presence of one minor, non-load-bearing self-citation rather than any actual circular reduction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted: the prediction error is defined externally, and the hyperparameter α is not tuned to prove the theorems. The upper bounds rely on standard algorithmic facts plus the definition of selection problems; the optimality claim additionally relies on UGC.

assumptions (4)
  • domain assumption Unique Games Conjecture (UGC).
    Used to derive the Khot-Regev hardness of Vertex Cover (Section 5.1, Proposition 11); the lower bounds in Theorems 13 and 14, and hence the paper's optimality claim for the class, are conditional on this conjecture.
  • standard math Mehlhorn's near-linear-time 2-approximation for Steiner Tree.
    Used in Section 2.1 and as the subroutine in Algorithm 2; the refined Steiner Tree analysis relies on its guarantees and running time.
  • standard math Matroid exchange property for spanning trees (Proposition 9).
    Used in the proof of Lemma 2 and Theorem 7 to compare edge costs between MST'α and MST.
  • standard math Goemans-Williamson V-join 2-approximation and triangle-inequality short-cutting.
    Used in Section 2.1 for Min-Weight Perfect Matching; the short-cutting step requires edge weights satisfying the triangle inequality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation Algorithms for Combinatorial Optimization with Predictions." pith.science (2026). https://pith.science/paper/GL3XNION

@misc{pith2026241116600,
  author       = {Pith},
  title        = {Pith review of: Approximation Algorithms for Combinatorial Optimization with Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GL3XNION}},
  note         = {Machine review of arXiv:2411.16600}
}
read the original 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 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 (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-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 prediction error we 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 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.

Figures

Figures reproduced from arXiv: 2411.16600 by the authors.

Figure 1
Figure 1. describes an instance with k = n − 1 terminals and a prediction with a single false￾negative edge of weight 1 + ϵ and a single false-positive edge of weight β > 2. Algorithm 2 with α ∈ [1,(1 + ϵ) −1 ) achieves approximation ratio approaching 2 as n increases. With α ∈ ( 1 1+ϵ , β 1+ϵ ), its approximation ratio is equal to 1. With α > β 1+ϵ , it approaches OPT+β OPT , which is equal to 2 if we choose β = OPT. This sh… view at source ↗
Figure 2
Figure 2. Experimental evaluation of our refined Steiner Tree algorithm from Section [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Improved Approximations for Hard Graph Problems using Predictions

    cs.LG 2025-05 conditional novelty 7.0 of 10

    Edge-level predictions that are only epsilon-better than random suffice to beat classical approximation barriers for vertex cover, set cover, maximum independent set, and max cut.

  2. The Importance of Encoder Choice:A Tabular-Image Study

    cs.LG 2026-07 conditional novelty 6.5 of 10

    Tabular encoder choice reorders multimodal rankings, can erase apparent fusion gains, and requires non-vanilla extraction for in-context learning models to avoid train-test representation shift.

  3. Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

    cs.DS 2025-02 accept novelty 6.0 of 10

    With pairwise predictions that are correct with probability just above 1/2, a class of NP-hard permutation problems (decomposable or c-local objectives) can be solved exactly in polynomial time using only O(n log n) queries.

Reference graph

Works this paper leans on

52 extracted references · 29 canonical work pages · cited by 3 Pith papers

  1. [1]

    Learning what to defer for maximum independent sets

    Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , volume 119 of Proceedings of Machine Learning Research, pages 134--144. PMLR , 2020. URL http://proceedings.mlr.press/v119/ahn20a.html

    work page 2020

  2. [2]

    Karger, and Marek Karpinski

    Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of NP -hard problems. J. Comput. Syst. Sci., 58 0 (1): 0 193--210, 1999. doi:10.1006/JCSS.1998.1605. Announced at STOC 1995

    arXiv 1999

  3. [3]

    Flow time scheduling with uncertain processing time

    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.1145/3406325.3451023

    arXiv 2021

  4. [4]

    Distortion-oblivious algorithms for minimizing flow time

    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.1137/1.9781611977073.13

    work page doi:10.1137/1.9781611977073.13 2022

  5. [5]

    Sorting with predictions

    Xingjian Bai and Christian Coester. Sorting with predictions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, 2023. URL http://papers.nips.cc/paper\_files/paper/2023/hash/544696ef4847c903376ed6ec58f3a703-Abstract-Conference.html

    work page 2023

  6. [6]

    Learning augmented energy minimization via speed scaling

    \' E tienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/af94ed0d6f5acc95f97170e3685f16c0-Ab...

    work page 2020

  7. [7]

    Parsimonious learning-augmented approximations for dense instances of NP -hard problems

    Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Parsimonious learning-augmented approximations for dense instances of NP -hard problems. In Forty-first International Conference on Machine Learning, ICML 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=AD5QC1BTJL

    work page 2024

  8. [8]

    A linear-time approximation algorithm for the weighted vertex cover problem

    Reuven Bar - Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms, 2 0 (2): 0 198--203, 1981. doi:10.1016/0196-6774(81)90020-1

    doi:10.1016/0196-6774(81)90020-1 1981

Show all 52 references
  1. [9]

    Machine learning for combinatorial optimization: A methodological tour d'horizon

    Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. Eur. J. Oper. Res., 290 0 (2): 0 405--421, 2021. doi:10.1016/J.EJOR.2020.07.063

    2021 doi

  2. [10]

    A universal error measure for input predictions applied to online graph problems

    Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti - Spaccamela, Nicole Megow, Leen Stougie, and Michelle Sweering. A universal error measure for input predictions applied to online graph problems. In Advances in Neural Information Processing Systems 35: Annual Confere...

    2022

  3. [11]

    The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration

    \' E douard Bonnet and Florian Sikora. The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration. In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 , volume 115 of LIPIcs, pages 26:1--26:15. Schloss Dags...

    2018 doi

  4. [12]

    Learning-augmented maximum independent set

    Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-augmented maximum independent set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024 , volume 317 of LIPIcs, pages 24:1--24:18. Schloss ...

    2024 doi

  5. [13]

    S teiner tree approximation via iterative randomized rounding

    Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvo , and Laura Sanit \` a . S teiner tree approximation via iterative randomized rounding. J. ACM , 60 0 (1): 0 6:1--6:33, 2013. doi:10.1145/2432622.2432628

    2013

  6. [14]

    Timothy M. Chan. Approximation schemes for 0-1 knapsack. In 1st Symposium on Simplicity in Algorithms, SOSA 2018 , volume 61 of OASIcs, pages 5:1--5:12. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2018. doi:10.4230/OASICS.SOSA.2018.5

    2018 doi

  7. [15]

    Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang

    Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML 2022 , volume 162 of Proceedings of Machine Learning Research, pages 3583--3602. PMLR , 2022. URL ht...

    2022

  8. [16]

    A nearly quadratic-time FPTAS for knapsack

    Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. A nearly quadratic-time FPTAS for knapsack. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024 , pages 283--294. ACM , 2024. doi:10.1145/3618260.3649730

    2024

  9. [17]

    The S teiner tree problem on graphs: Inapproximability results

    Miroslav Chleb \' k and Janka Chleb \' kov \' a . The S teiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci., 406 0 (3): 0 207--214, 2008. doi:10.1016/J.TCS.2008.06.046

    2008 doi

  10. [18]

    Worst-case analysis of a new heuristic for the travelling salesman problem

    Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum, 3 0 (1), 2022. doi:10.1007/S43069-021-00101-Z. Announced as a technical report in 1976

    2022 doi

  11. [19]

    Learning-augmented approximation algorithms for maximum cut and related problems

    Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Learning-augmented approximation algorithms for maximum cut and related problems. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, NeurIPS 2024, 2024. URL h...

    2024

  12. [20]

    George B. Dantzig. Discrete-variable extremum problems. Operations Research, 5 0 (2): 0 266--288, 1957. doi:10.1287/opre.5.2.266

    1957 doi

  13. [21]

    Predictive flows for faster F ord- F ulkerson

    Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster F ord- F ulkerson. In International Conference on Machine Learning, ICML 2023 , volume 202 of Proceedings of Machine Learning Research, pages 7231--7248. PMLR , 2023. URL https://p...

    2023

  14. [22]

    Faster matchings via learned duals

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 10393--10...

    2021

  15. [23]

    Algorithms with prediction portfolios

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022. URL ht...

    2022

  16. [24]

    Secretaries with advice

    Paul D \" u tting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. Math. Oper. Res., 49 0 (2): 0 856--879, 2024. doi:10.1287/MOOR.2023.1384. Announced at EC 2021

    2024

  17. [25]

    Maximum matching and a polyhedron with 0,1 -vertices

    Jack Edmonds. Maximum matching and a polyhedron with 0,1 -vertices. J. of Res. the Nat. Bureau of Standards, 69 B: 0 125--130, 1965

    1965

  18. [26]

    Ergun, Zhili Feng, Sandeep Silwal, David P

    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 Representations, ICLR 2022 . OpenReview.net, 2022. URL https://openreview.net/forum?id=X8cLTHexYyY

    2022

  19. [27]

    Using machine learning predictions to speed-up D ijkstra's shortest path algorithm

    Willem Feijen and Guido Sch \" a fer. Using machine learning predictions to speed-up D ijkstra's shortest path algorithm. CoRR, abs/2112.11927, 2021. URL https://arxiv.org/abs/2112.11927

    2021 arXiv

  20. [28]

    Harold N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms , pages 434--443. SIAM , 1990. URL http://dl.acm.org/citation.cfm?id=320176.320229

    1990

  21. [29]

    Approximate cluster recovery from noisy labels

    Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi - Fard, and Ola Svensson. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1463--1509. PMLR , 2022. URL https://proceedings.mlr.pres...

    2022

  22. [30]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput. , 24 0 (2): 0 296--317, 1995. doi:10.1137/S0097539793242618. Announced at SODA 1992

    1995 doi

  23. [31]

    Clique is hard to approximate within n\( ^ 1-epsilon \)

    Johan H stad. Clique is hard to approximate within n\( ^ 1-epsilon \). Acta Mathematica, 182 0 (1): 0 105--142, 1999. doi:10.1007/BF02392825. Announced at FOCS 1996

    1999 doi

  24. [32]

    Online page migration with ML advice

    Piotr Indyk, Frederik Mallmann - Trenn, Slobodan Mitrovic, and Ronitt Rubinfeld. Online page migration with ML advice. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022 , volume 151 of Proceedings of Machine Learning Research, pages 1655--1670...

    2022

  25. [33]

    Joshi, Quentin Cappart, Louis - Martin Rousseau, and Thomas Laurent

    Chaitanya K. Joshi, Quentin Cappart, Louis - Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints An Int. J., 27 0 (1-2): 0 70--98, 2022. doi:10.1007/S10601-022-09327-Y

    2022 doi

  26. [34]

    Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85--103. Plenum Press, New York, 1972. doi:10.1007/978-1-4684-2001-2\_9

    1972 doi

  27. [35]

    Vertex cover might be hard to approximate to within 2-epsilon

    Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74 0 (3): 0 335--349, 2008. doi:10.1016/J.JCSS.2007.06.019

    2008 doi

  28. [36]

    T. Koch, A. Martin, and S. Vo . SteinLib : An updated library on S teiner tree problems in graphs. Technical Report ZIB-Report 00-37, Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin, Takustr. 7, Berlin, 2000. URL https://steinlib.zib.de/

    2000

  29. [37]

    Combinatorial Optimization: Theory and Algorithms

    Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 5 edition, 2012. doi:10.1007/978-3-642-24488-9

    2012 doi

  30. [38]

    Kou, George Markowsky, and Leonard Berman

    Lawrence T. Kou, George Markowsky, and Leonard Berman. A fast algorithm for S teiner trees. Acta Informatica, 15: 0 141--145, 1981. doi:10.1007/BF00288961

    1981 doi

  31. [39]

    Chi, Jeffrey Dean, and Neoklis Polyzotis

    Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018 , pages 489--504. ACM , 2018. doi:10.1145/3183713.3196909

    2018

  32. [40]

    Speeding up B ellman F ord via minimum violation permutations

    Silvio Lattanzi, Ola Svensson, and Sergei Vassilvitskii. Speeding up B ellman F ord 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 htt...

    2023

  33. [41]

    Algorithms with predictions

    Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https://algorithms-with-predictions.github.io, 2022. Accessed 22 May 2024

    2022

  34. [42]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM , 68 0 (4): 0 24:1--24:25, 2021. doi:10.1145/3447579. Announced at ICML 2018

    2021 doi

  35. [43]

    (1 - \( \) )-approximation of knapsack in nearly quadratic time

    Xiao Mao. (1 - \( \) )-approximation 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.1145/3618260.3649677

    2024

  36. [44]

    A faster approximation algorithm for the S teiner problem in graphs

    Kurt Mehlhorn. A faster approximation algorithm for the S teiner problem in graphs. Inf. Process. Lett., 27 0 (3): 0 125--128, 1988. doi:10.1016/0020-0190(88)90066-X

    1988 doi

  37. [45]

    Algorithms with predictions

    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:10.1017/9781108637435.037

    2020 doi

  38. [46]

    Thy Dinh Nguyen, Anamay Chaturvedi, and Huy L. Nguyen. Improved learning-augmented algorithms for k-means and k-medians clustering. In The Eleventh International Conference on Learning Representations, ICLR 2023 . OpenReview.net, 2023. URL https://openreview.net/forum?id=dCSFiAl\_VO3

    2023

  39. [47]

    Learning-augmented maximum flow

    Adam Polak and Maksym Zub. Learning-augmented maximum flow. Information Processing Letters, 186: 0 106487, 2024. ISSN 0020-0190. doi:10.1016/j.ipl.2024.106487

    2024

  40. [48]

    Improving online algorithms via ML predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, pages 9684--9693, 2018. URL https://proceeding...

    2018

  41. [49]

    Source code of the CIMAT solver for the S teiner tree problem

    Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin Enrique Villalobos López, and Carlos Segura González. Source code of the CIMAT solver for the S teiner tree problem. https://github.com/HeathcliffAC/SteinerTreeProblem, 2018. Accessed 22 May 2024

    2018

  42. [50]

    Discrete-convex-analysis-based framework for warm-starting algorithms with predictions

    Shinsaku Sakaue and Taihei Oki. Discrete-convex-analysis-based framework for warm-starting algorithms with predictions. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022. URL http://pape...

    2022

  43. [51]

    Reinforcement learning for integer programming: Learning to cut

    Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020 , volume 119 of Proceedings of Machine Learning Research, pages 9367--9376. PMLR , ...

    2020

  44. [52]

    Williamson and David B

    David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0-521-19527-0

    2011

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.