Pith. sign in

REVIEW 1 major objections 3 minor 46 references

Asking a predictor what to ignore, then verifying each answer with a polynomial-time verifier, makes offline approximation safe and its pruning parameters learnable.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

A verification layer around learned pruning of NP-hard problems yields prediction-independent worst-case guarantees and PAC-learnable parameters.

T0 review reviewed 2026-08-02 challenge →

load-bearing objection Genuinely new verifier-gated learning theory for offline predictions, with an honest paper that overclaims in the abstract on two conditional certificates. the 1 major comments →

arxiv 2607.14545 v1 pith:ZM44KIT4 submitted 2026-07-16 cs.LG

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

Haifeng Li , Mo Hai This is my paper
classification cs.LG MSC 68Q3268W2590C27
keywords algorithms with predictionslearning-augmented algorithmscertificate verificationPAC learningsample complexityconfidence filteringLP degeneracyoffline approximation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The paper proposes CASP: instead of asking a predictor to point at a near-optimal solution, ask it which parts of the search space can be pruned, and accept each answer only after a sound polynomial-time verifier confirms it. The central claim is that verification, not the sign of the prediction signal, is the resource that makes learning-augmented offline approximation safe: correctness never depends on prediction quality, and the induced loss class is uniformly bounded. As a result, certificate parameters are PAC-learnable from roughly O~(epsilon^{-2} log K) samples, while the equivalent unverified 'commit the prediction' class has no distribution-free rate. The paper also proves that filtering noisy predictions by verifiable confidence dominates the standard min-combiner with a closed-form margin, and that predictions remain useful even alongside the LP because they break ties on degenerate optimal faces where every symmetric LP policy stalls. Empirical tests on five problems confirm that verified deployment of the same trained predictions loses nothing under distribution shift where unverified pruning loses up to 26% of the optimum.

Core claim

CASP's central claim is that a certificate system—an assertion language, a sound polynomial-time verifier, and a pruning operator—lets an offline approximation algorithm consume machine-learned advice as 'what may be safely ignored' rather than 'what to do.' Each accepted certificate is either OPT-preserving or rho-approximation-safe, and Algorithm 1 combines them with a classical fallback to return a feasible solution of cost at most max(rho * alpha_red, alpha) times OPT, independent of prediction quality. This uniform bound makes the loss class uniformly bounded, which is why certificate parameters are learnable from O~(epsilon^{-2} log K) samples, whereas the structurally identical bare-c

What carries the argument

The central object is a certificate system (L, V, P): an assertion language, a sound polynomial-time verifier, and a pruning operator, with safety graded into OPT-preserving and rho-approximation-safe classes. The load-bearing identity is Theorem 3's robustness bound c(S) <= max(rho * alpha_red, alpha) * OPT(I), which renders the loss class uniformly bounded and thereby powers the PAC sample-complexity results and the confidence-filter margins. On the prediction side, the verifiable confidence signal sigma_i—typically the LP value the verifier already computes—is the mechanism that lets a filter commit only high-confidence parts of a noisy prediction and dominate the min-combiner.

Load-bearing premise

The load-bearing premise is that useful pruning certificates can be proposed and verified efficiently—if the predictor cannot generate certificates that both pass the verifier and shrink the instance, CASP collapses to its fallback—and, for the exactness claims on Set Cover and Facility Location, that an integer optimum lies in the LP support (condition Sup), which the paper admits is not polynomially verifiable.

What would settle it

Construct an instance I, a sound verifier, and a verified certificate phi with OPT(I_phi)+cfix < OPT(I), or exhibit an execution where Algorithm 1 returns a solution costing more than max(rho*alpha_red, alpha)*OPT(I); either would falsify the core robustness claim. Equivalently, exhibit a bounded-frequency family with bounded pseudo-dimension where the unverified commitment class does admit a distribution-free uniform-convergence rate despite its unbounded range, contradicting Lemma 4.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Correctness of CASP is independent of prediction quality: wrong certificates are rejected by the verifier, and the fallback preserves the classical worst-case guarantee.
  • Certificate parameters such as pruning thresholds are learnable from O~(epsilon^{-2} log K) samples, while unverified commitment has no distribution-free rate and, under cost spread R, requires Omega(R/epsilon^2) samples.
  • Filtering noisy solution predictions by verifiable confidence dominates the standard min-combiner, with an exact margin that grows from zero with small noise and is capped by the fallback gap.
  • Predictions add value even when an LP is available: they break ties on degenerate optimal faces, which no symmetric LP-commit policy can do.
  • On recognizable classes, such as graphs with logarithmic half-integral cores or facility-integral LP optima, CASP emits checkable proofs of optimality and can solve NP-hard instances in polynomial time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The certificate-plus-verifier interface is generic: any classical presolve or reduction that can be expressed as a verifiable assertion could be made prediction-augmented in the same way, even for problems not covered by the five instantiations.
  • The two-threshold filter suggests a general design principle: separate gates for prediction confidence and verifier-computed confidence, which may help other pipelines that combine learned and analytic signals with a fallback.
  • Exactness on Set Cover and Facility Location rests on condition Sup—an integer optimum supported in the LP support—which the paper admits is not polynomially verifiable; without Sup, those certificates degrade to f- or Delta-safety, so a deployment lacking ground truth should treat exactness as conditional unless a verifiable trigger like facility-integrality fires.
  • A testable extension is to train certificate generators on new NP-hard problems where classical reductions already exist, using the net-speedup condition as a concrete criterion for when verified pruning pays.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 3 minor

Summary. This paper introduces CASP, a learning-augmented framework for offline NP-hard optimization in which the predictor proposes negative-signal certificates—regions of the search space that may be pruned—and a polynomial-time verifier accepts only assertions it can prove. It defines graded safety (OPT-preserving vs. ρ-approximation-safe), proves core composition and robustness theorems (Thms 1–5), instantiates the framework on five problems using classical reductions, develops PAC bounds for certificate thresholds, and derives closed-form margins for confidence filtering over min-combining. It also delineates interface contrasts (certified optimality, bounded loss) and their collapse under a fair min-combiner, with experiments E1–E14 including trained predictors under distribution shift. The paper is unusually candid about limitations, including the vacuous Markov floor, the unverifiable Sup condition, and a presolve audit caveat for speedup claims.

Significance. If correct, the core design idea—verification rather than prediction sign as the resource—is an important and potentially influential contribution to algorithms with predictions. The paper's strengths include detailed self-contained appendix proofs; explicit closed-form computations on decomposable families (Thms 16–19) that are then empirically re-derived by Monte-Carlo (E14); and an honest treatment of where guarantees are conditional, most notably the unverifiable Sup condition (Rem. 5) and the collapse of the interface contrasts under a fair adversary (Sec. 7.4). The boundedness/PAC contrast and the filtering margin theorems are substantive, and the experiments are mapped to specific theoretical statements. The main weakness is that the abstract and §1.2 advertise the correctness/exactness guarantees more broadly than the conditional certificates in Sections 4.1 and 4.3 actually support.

major comments (1)
  1. [Abstract; §1.2; §4.1 (Thm 7, Rem 5, Table 1); Algorithm 1] The abstract and §1.2 state the guarantee unconditionally ('correctness never depends on prediction quality'; 'a wrong prediction is at worst rejected and never causes an incorrect pruning'). For the Set Cover and Facility Location complementary-slackness certificates, the verifier checks only the assertion φ_CS (e.g., Σ_{e∈S} y*_e < c_S), which implies x*_S=0; it does not check that any integer optimum survives. OPT-preservation requires condition Sup (some integer optimum S* with supp(S*)⊆supp(x*)), which Remark 5 explicitly says is not polynomially verifiable. Algorithm 1 returns the reduced solution without fallback comparison whenever the reduced solve succeeds; if Sup fails, all integer optima can be pruned, so OPT(I_φ)>OPT(I) and the ρ=1 case of Theorem 3 does not apply. The f-/Δ-safe bounds (Thms 6 and 10) preserve the bounded-loss/PAC core, but exactness, 'never worse than the f
minor comments (3)
  1. [Abstract; §8.13 (E13)] The abstract says the verified deployment 'loses nothing' under distribution shift, but E13 reports zero infeasibility with a quality gap of at most 0.071% on Set Cover and zero loss on Knapsack. Please qualify the headline claim to match the reported numbers.
  2. [§8.5, Table 4] The text notes that the Set Cover timing columns predate the presolve audit, but Table 4 prints them alongside audited columns without a marker. Add an explicit 'pre-audit' annotation in the table itself so provenance is not read as current evidence.
  3. [Appendix A.17 (Thm 14)] The proof invokes the Milnor–Thom/Warren sign-pattern bound without a citation. Add the standard reference (e.g., Milnor 1964; Warren 1968) or a textbook pointer for the cell-count bound.

Circularity Check

1 steps flagged

One acknowledged near-definitional containment in the confidence-filter domination; the core safety, PAC, and margin results are not circular.

specific steps
  1. self definitional [Section 6 / Theorem 15(ii) and proof A.18; Section 6.1]
    "Theorem 15(ii) alone is close to definitional, since the filter family contains the min-combiner at θ = 0; the content lies in the size of the margin and its scaling with noise. ... (ii) The family {ℓcf θ }containsℓcf 0 =ℓmc, so minθ ED[ℓcf θ ]≤ED[ℓcf 0 ] =ED[ℓmc]."

    The claimed weak domination of the confidence filter over the min-combiner is literally an inclusion argument: the filter family was defined so that θ=0 reproduces the min-combiner, so the minimum over θ is at most the min-combiner's loss. No property of verification, confidence, or learning is used. The paper explicitly acknowledges this and directs the content to the strict margin results, which are derived by independent arithmetic on explicit families. The step is therefore a minor definitional containment, not a load-bearing prediction of the paper's central claims.

full rationale

The paper's main derivation chain is self-contained and non-circular. The bounded-loss guarantee (Theorem 3) is derived from the fallback factor α and the defined ρ-safety of adopted prunings; the PAC bounds (Theorems 13–14) are standard bounded-range uniform-convergence applications with the range constant computed from that bound, not fitted to the data. The learnability contrast (Theorems 21–22, Lemma 4) is supported by explicit constructions and a fair-combiner collapse (Theorem 23, Corollary 2), so it does not rest on an imported uniqueness theorem or on self-citation. There are no load-bearing self-citations and no ansatz smuggled in via citation: the certificates are explicitly classical reductions, and the paper states that none of the individual reductions is new. The complementary-slackness certificates for Set Cover and Facility Location depend on the unverifiable condition Sup, which weakens the unconditional OPT-preservation claims for those instantiations; however, this is a correctness/qualification issue explicitly disclosed by the authors (Remark 5, Table 1), not a circular step, because Sup is not assumed as an input to the derivation. The one near-definitional step is Theorem 15(ii), whose weak domination is by construction since the filter family contains the min-combiner at θ=0; the paper itself flags this, and the substantive contributions — the exact margin, the degeneracy separation, and the boundedness contrast — are computed independently. External benchmarks and an independent verifier reimplementation give the empirical claims independent support. Overall circularity is therefore low.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 0 invented entities

No ad hoc fitted constants are used in the central derivations; thresholds are either derived (tau <= 1/f, theta=1/2) or are the subject of the PAC learning bounds. The framework introduces a formal certificate language, verifier, and pruning operator, which are methodological devices rather than postulated physical or mathematical entities. The only avowedly unverifiable assumption is Sup, which the paper flags explicitly.

free parameters (2)
  • Pruning threshold tau = tau <= 1/f in theory; ERM-chosen tau=0.02 in E4
    The safe threshold is derived from the LP-rounding frequency f, not fitted to benchmarks; experimental values are learned from training samples, and the PAC theorems bound generalization for any such threshold.
  • Filter threshold theta (and theta1, theta2 for CF+) = theta=1/2 or theta in (1/2,1] in the constructed families; ERM-selected values in E12/E12'
    The theoretical margins are stated for allowed thresholds; the experimental deployments fit the threshold by ERM. The values do not enter the central derivations as hidden fitted constants.
axioms (6)
  • domain assumption Verifier soundness: V(I, phi, w)=1 implies phi is true on I (Definition 2).
    This is the keystone of the framework; if violated, accepted certificates could prune incorrectly and the worst-case guarantee collapses.
  • domain assumption Polynomial-time feasibility predicate and polynomial-time verifier (Definition 1).
    CASP assumes certificates can be checked in polynomial time; otherwise the framework is not an algorithm.
  • standard math Classical results: Nemhauser-Trotter persistency and half-integrality; LP duality and complementary slackness; LP rounding bounds for Set Cover and Facility Location; Dantzig reduced-cost bounds.
    Used for the five instantiations in Section 4; cited and not re-proved.
  • ad hoc to paper Condition Sup: some integer optimum S* satisfies supp(S*) subset of supp(x*) (Theorem 7, Remark 5).
    The authors label this unverifiable; it is needed for OPT-preservation of the complementary-slackness certificates on Set Cover and Facility Location.
  • standard math Pseudo-dimension and uniform-convergence machinery, including Pollard-type bounds and Milnor-Thom/Warren sign-pattern bounds.
    Used in Section 5 and Theorem 14; cited as standard background.
  • domain assumption For the empirical zero-mismatch claims, the SCIP solver and the independent verifier reimplementation are correct.
    Support for the experimental claims; the paper ships an independent checker for the verifier and reports audit protocols, but no external formal verification is provided.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees." pith.science (2026). https://pith.science/paper/ZM44KIT4

@misc{pith2026260714545,
  author       = {Pith},
  title        = {Pith review of: CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZM44KIT4}},
  note         = {Machine review of arXiv:2607.14545}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from $\tilde O(\varepsilon^{-2}\log K)$ samples ($K$ the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread $R$, none below $\Omega(R/\varepsilon^2)$. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Figures

Figures reproduced from arXiv: 2607.14545 by Haifeng Li, Mo Hai.

Figure 1
Figure 1. Figure 1: E2 (all 600 Set Cover instances; descriptive). (a) Empirical pruning rate increases with frequency f. (b) Distribution of realized rates against the Markov floor of Remark 4, which equals 0 on all 600 instances; the panel documents the headroom (min 0.137, median 0.82) rather than validating a vacuous bound [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: E1: distribution of the NT residual-core fraction on the real DIMACS graphs. The certificate prunes only where structure exists; on real ORLIB-cap Facility Location the facility￾integral trigger fires on all 37 instances with zero mismatch. This measures per-bucket threshold vectors θ ∈ R p . The loss is uniformly bounded by 1.14 for all p ∈ {2, 4, 8}, the property behind Theorem 14, and the generalization… view at source ↗
Figure 3
Figure 3. Figure 3: E4: learnability. (a) cost-ratio landscape over the single threshold τ : on this benign distribution the landscape is flat (every τ in the safe grid ties at 1.0007), so ERM attains zero excess test error from N=5 trivially; the discriminating version is E4′′ . (b) multi-parameter generalization gap vs. N: on the heavy-tailed distribution of E4′′ (solid) the gap is ordered by p and vanishes as N grows, the … view at source ↗
Figure 4
Figure 4. Figure 4: E5: safe rate vs. certificate noise η. CASP (SC and VC) stays at 100% for all η; safety is independent of the noise level because the verifier and fallback, not the parameter, provide it (Theorem 5). per solve) the full instance times out on 31/40. On the 9 instances both arms solve, the net speedup (LP and pruning time charged to CASP) is mean 13.7×, median 12.9×, max 21.3×, with f-safe gaps ≤ 0.35% (OPT-… view at source ↗
Figure 5
Figure 5. Figure 5: E6: net speedup, full data. (a) Distribution by certificate type and problem (log scale, bars = means); OPT-preserving certificates dominate. (b) Speedup rises with pruning rate; color = OPT-preserving vs. f-approx, marker = problem. 8.7 E11: Steiner Tree E11 evaluates the Steiner certificates of Section 4.5 (R1/R2 applied iteratively, re-verified after each deletion) on the SteinLib benchmark. We solve bo… view at source ↗
Figure 6
Figure 6. Figure 6: E9 (Theorem 12): residual core fraction per Knapsack instance type; points are instances, bars are means. The core collapses on structured types and stays full on the hard correlated types, with zero mismatch throughout [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The two interface contrasts (Section 7). [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: E10′ (fair rerun). Three arms on the same instances: the bare commitment degrades with noise, its min-combined variant is flat at the fallback ratio (Theorem 23), CASP is flat at 1.002 and certifies 93%. 8.9 E10′ : a fair three-arm rerun We apply the fairness standard of Section 7.4 to E10 itself. On 30 synthetic VC instances and η ∈ {0, . . . , 0.5}, the baseline of Antoniadis et al. (2025) as published d… view at source ↗
Figure 9
Figure 9. Figure 9: E12: verifiable confidence filtering dominates the min-combiner. (a) On Set Cover the min-combiner is pinned at the fallback (1.10 at every noise level η) while the confidence￾filter stays near-optimal; the shaded band is the domination margin. (b) On Vertex Cover the confidence-filter is nearly noise-invariant (≈ 1.03) while the min-combiner degrades toward the fallback, so the margin grows with η (to 0.2… view at source ↗
Figure 10
Figure 10. Figure 10: E12′ . (a) Set Cover, flip noise: the single-threshold filter (CF) dominates the min￾combiner everywhere but crosses below the prediction-free LP-threshold arm at high noise; the two-threshold filter CF+ (Proposition 4) tracks the best of both and improves strictly on 18 of 21 (model,η) points. (b) The prediction’s added value by LP-degeneracy tertile: it concentrates on degenerate instances, the empirica… view at source ↗
Figure 11
Figure 11. Figure 11: E14(a): Theorem 16 recomputed by Monte Carlo. Measured min-combiner-vs￾filter margins (points, ±3 s.e.) against the closed form min{η[(C − η) + β(1 − η) 2 ], β}/(1 + 2β) (curves), per β panel at n=5000; the dotted line is the fallback-gap cap β/(1 + 2β) (an upper bound on the margin, attained only where the unsaturated branch reaches β). 0.0 0.2 0.4 0.6 0.8 noise rate 0.0 0.2 0.4 0.6 p er-g a d g et m arg… view at source ↗
Figure 12
Figure 12. Figure 12: E14(b): Theorem 17 recomputed by Monte Carlo. Measured per-gadget margin of the filter over the LP-commit policy (points) against the closed form (curves) under both σ￾canonicalizations; dotted lines are the proven floors, never crossed. theoretical 1/3. Degeneracy (Theorem 17). Across the corresponding grid on Hm,n(ε) (720 rows, both σ-canonicalizations of Remark 9), the measured per-gadget margin matche… view at source ↗
Figure 13
Figure 13. Figure 13: E13(a): verified vs unverified deployment of the same trained predictor under distribution shift. (a) Set Cover, OOD (f→10, 20): unverified deletion is infeasible on up to 10/30 instances depending on the prediction threshold; the verified arm is never infeasible and its gap stays within the certified f-safe budget. (b) Knapsack: unverified exclusion forfeits optimality frequently already in distribution … view at source ↗
Figure 14
Figure 14. Figure 14: E13(b): learned predictors through the filter. (a) Low-degeneracy VC: an F1 ≈ 0.75 GNN committed wholesale costs +15–33%; filtered, it ties LP-commit — the filter learns to ignore it (Proposition 3). (b) High-degeneracy tagged twins: the GNN reads side information the LP cannot express and CF+ beats every LP-commit policy by +0.151 (Theorem 17, learning-side). zero noise and growing with small noise (Theo… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 5 linked inside Pith

  1. [1]

    Improved approximations for hard graph problems using predictions

    Anders Aamand, Justin Y Chen, Siddharth Gollapudi, Sandeep Silwal, and Hao Wu. Improved approximations for hard graph problems using predictions. arXiv preprint arXiv:2505.23967, 2025

    Pith/arXiv arXiv 2025

  2. [2]

    Presolve reductions in mixed integer programming

    Tobias Achterberg, Robert E Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32 0 (2): 0 473--506, 2020

    2020

  3. [3]

    Approximation algorithms for combinatorial optimization with predictions

    Antonios Antoniadis, Marek Eli \'a s, Adam Polak, and Moritz Venzin. Approximation algorithms for combinatorial optimization with predictions. In International Conference on Learning Representations, volume 2025, pages 49039--49052, 2025

    2025

  4. [4]

    Data-driven algorithm design

    Maria-Florina Balcan. Data-driven algorithm design. arXiv preprint arXiv:2011.07177, 2020

    Pith/arXiv arXiv 2011

  5. [5]

    Learning to branch

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344--353. PMLR, 2018

    2018

  6. [6]

    How much data is sufficient to learn high-performing algorithms? Journal of the ACM, 71 0 (5): 0 1--58, 2024

    Maria-Florina Balcan, Dan Deblasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? Journal of the ACM, 71 0 (5): 0 1--58, 2024

    2024

  7. [7]

    The primal-dual method for learning augmented algorithms

    Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33: 0 20083--20094, 2020

    2020

  8. [8]

    Polynomial time learning-augmented algorithms for np-hard permutation problems

    Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, and Michalis Xefteris. Polynomial time learning-augmented algorithms for np-hard permutation problems. arXiv preprint arXiv:2502.00841, 2025

    Pith/arXiv arXiv 2025

  9. [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. European Journal of Operational Research, 290 0 (2): 0 405--421, 2021

    2021

  10. [10]

    warm start

    Avrim Blum and Vaidehi Srinivas. Competitive strategies to use “warm start” algorithms with predictions. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3775--3801. SIAM, 2025

    2025

  11. [11]

    Combinatorial optimization and reasoning with graph neural networks

    Quentin Cappart, Didier Ch \'e telat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veli c kovi \'c . Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24 0 (130): 0 1--61, 2023

    2023

  12. [12]

    Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut

    Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. Advances in Neural Information Processing Systems, 37: 0 25036--25060, 2024

    2024

  13. [13]

    A greedy heuristic for the set-covering problem

    Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4 0 (3): 0 233--235, 1979

    1979

  14. [14]

    Max-cut with -accurate predictions

    Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Max-cut with -accurate predictions. arXiv preprint arXiv:2402.18263, 2024

    Pith/arXiv arXiv 2024

  15. [15]

    Parameterized Algorithms

    Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015

    2015

  16. [16]

    Faster matchings via learned duals

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in neural information processing systems, 34: 0 10393--10406, 2021

    2021

  17. [17]

    Algorithms with prediction portfolios

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. Advances in neural information processing systems, 35: 0 20273--20286, 2022

    2022

  18. [18]

    Analytical approach to parallel repetition

    Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624--633, 2014

    2014

  19. [19]

    Reduction tests for the steiner problem in grapsh

    Cees W Duin and Anton Volgenant. Reduction tests for the steiner problem in grapsh. Networks, 19 0 (5): 0 549--567, 1989

    1989

  20. [20]

    Safe feature elimination in sparse supervised learning technical report no

    L El Ghaoui, V Viallon, and T Rabbani. Safe feature elimination in sparse supervised learning technical report no. Technical report, UCB/EECS-2010--126, EECS Department, University of California, Berkeley, 2010

    2010

  21. [21]

    A dual-based procedure for uncapacitated facility location

    Donald Erlenkotter. A dual-based procedure for uncapacitated facility location. Operations Research, 26 0 (6): 0 992--1009, 1978

    1978

  22. [22]

    A threshold of ln n for approximating set cover

    Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45 0 (4): 0 634--652, 1998

    1998

  23. [23]

    Scip-jack—a solver for stp and variants with parallelization extensions

    Gerald Gamrath, Thorsten Koch, Stephen J Maher, Daniel Rehfeldt, and Yuji Shinano. Scip-jack—a solver for stp and variants with parallelization extensions. Mathematical Programming Computation, 9 0 (2): 0 231--296, 2017

    2017

  24. [24]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123--134, 2016

    2016

  25. [25]

    Approximation algorithms for the set covering and vertex cover problems

    Dorit S Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on computing, 11 0 (3): 0 555--556, 1982

    1982

  26. [26]

    Reduction algorithm for zero-one single knapsack problems

    Giorgio P Ingargiola and James F Korsh. Reduction algorithm for zero-one single knapsack problems. Management science, 20 0 (4-part-i): 0 460--463, 1973

    1973

  27. [27]

    Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation

    Kamal Jain and Vijay V Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM (JACM), 48 0 (2): 0 274--296, 2001

    2001

  28. [28]

    Vertex cover might be hard to approximate to within 2-

    Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- . Journal of Computer and System Sciences, 74 0 (3): 0 335--349, 2008

    2008

  29. [29]

    Fine-grained search space classification for hard enumeration variants of subset problems

    Juho Lauri and Sourav Dutta. Fine-grained search space classification for hard enumeration variants of subset problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2314--2321, 2019

    2019

  30. [30]

    A 1.488 approximation algorithm for the uncapacitated facility location problem

    Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222: 0 45--58, 2013

    2013

  31. [31]

    -approximations with minimum packing constraint violation

    Jyh-Han Lin and Jeffrey Scott Vitter. -approximations with minimum packing constraint violation. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 771--782, 1992

    1992

  32. [32]

    L2p-mip: Learning to presolve for mixed integer programming

    Chang Liu, Zhichen Dong, Haobo Ma, Weilin Luo, Xijun Li, Bowen Pang, Jia Zeng, and Junchi Yan. L2p-mip: Learning to presolve for mixed integer programming. In The Twelfth International Conference on Learning Representations, 2024

    2024

  33. [33]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68 0 (4): 0 1--25, 2021

    2021

  34. [34]

    Knapsack problems: algorithms and computer implementations

    Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990

    1990

  35. [35]

    Certifying algorithms

    Ross M McConnell, Kurt Mehlhorn, Stefan N \"a her, and Pascal Schweitzer. Certifying algorithms. Computer Science Review, 5 0 (2): 0 119--161, 2011

    2011

  36. [36]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65 0 (7): 0 33--35, 2022

    2022

  37. [37]

    Solving mixed integer programs using neural networks

    Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020

    Pith/arXiv arXiv 2012

  38. [38]

    Gap safe screening rules for sparsity enforcing penalties

    Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Gap safe screening rules for sparsity enforcing penalties. Journal of Machine Learning Research, 18 0 (128): 0 1--33, 2017

    2017

  39. [39]

    Vertex packings: structural properties and algorithms

    George L Nemhauser and Leslie E Trotter Jr. Vertex packings: structural properties and algorithms. Mathematical Programming, 8 0 (1): 0 232--248, 1975

    1975

  40. [40]

    Where are the hard knapsack problems? Computers & Operations Research, 32 0 (9): 0 2271--2284, 2005

    David Pisinger. Where are the hard knapsack problems? Computers & Operations Research, 32 0 (9): 0 2271--2284, 2005

    2005

  41. [41]

    Improved algorithms for the steiner problem in networks

    Tobias Polzin and Siavash Vahdati Daneshmand. Improved algorithms for the steiner problem in networks. Discrete Applied Mathematics, 112 0 (1-3): 0 263--300, 2001

    2001

  42. [42]

    Improving online algorithms via ml predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018

    2018

  43. [43]

    Beyond the worst-case analysis of algorithms

    Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021

    2021

  44. [44]

    Approximation algorithms for facility location problems

    David B Shmoys, \'E va Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 265--274, 1997

    1997

  45. [45]

    Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems

    Yuan Sun, Xiaodong Li, and Andreas Ernst. Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems. IEEE transactions on pattern analysis and machine intelligence, 43 0 (5): 0 1746--1760, 2021

    2021

  46. [46]

    Optimal robustness-consistency trade-offs for learning-augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Advances in Neural Information Processing Systems, 33: 0 8042--8053, 2020

    2020

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.