{"id":"e98c1837-0a9a-4e61-bcb4-259f62f94b8e","arxiv_id":"2411.16600","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A black-box method converts any approximation algorithm into a learning-augmented one with a smooth trade-off between prediction error and solution quality, with matching lower bounds.","lead":"This paper shows a general trick: feed a machine-learning prediction into any existing near-optimal fast algorithm, and the algorithm's quality degrades gracefully as the prediction gets worse. For a large class of optimization problems, the paper proves this trick is the best possible unless a famous complexity conjecture is false.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The class-wide optimality claim rests on an unproved unweighted gadget in Theorem 13; the black-box upper bound (Theorem 2) is sound, but Theorems 13–14 need a quantitative proof of the copy-count construction.","rationale":"The reader's weakest assumption names UGC and the sketched unweighted gadget. I agree that the gadget is the real soft spot; the UGC dependence is explicitly stated and standard, so it is a conditional rather than an internal flaw. The upper-bound half of the paper is in good shape: Theorem 2's proof is a short and valid weight-modification argument, the applications (Vertex Cover, Steiner Tree, V-join/Matching, Knapsack) are consistent, and the refined Steiner algorithm and experiments are independently interesting. The paper gives credit for those parts. My concern is that the 'optimal for the class as a whole' headline rests on Theorems 13 and 14, and the current proof of Theorem 13 contains only a one-paragraph sketch of the weighted-to-unweighted reduction. The terms 'roughly' and 'approximately' are doing real work: exact copy counts and error decomposition are needed to preserve the constants in the UGC gap. This is a fixable but essential gap, so the paper should be accepted only after the reduction is written out. Because the reader already returned CONDITIONAL, my stress-test does not change the verdict; it sharpens the reason. No ad hominem is implied; the issue is purely the missing calculation in Section 5.2.","tokens_in":23791,"tokens_out":27957,"duration_ms":251464,"concrete_test":"Write the disjoint-union instance of Theorem 13 with exact integer copy counts a,b,c. Compute OPT = a·(n/2) + (b+c)|X*|, η+ = b(n−|X*|), η− = c|X*|, and L = a·(n/2) + (b+c)(1−δ)n, the minimum possible total cost if every G+ and G− copy has cover size at least (1−δ)n. Verify algebraically that for all |X*|∈[(1−δ)n/2,(1+δ)n/2], all x,y≥0 with x+y≤1, and the proposed a,b,c (allowing integer rounding), one has η+/OPT≤x, η−/OPT≤y, and (1+x+y−ε)·OPT < L whenever ε = x+y−f(x,y) > 0. Also redo for y=0 and x=0. If any inequality fails, the gadget does not preserve the promised ratios and the lower bound needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 is correct: zeroing predicted weights and running any ρ-approximation yields the advertised additive bound, and the examples follow. The load-bearing gap is in the lower-bound proof of Theorem 13, specifically the final paragraph that converts the weighted instance into an unweighted one by taking 'roughly' 1/(x′y′) copies of G0, 1/((1−x′−y′)y′) copies of G+, and 1/((1−x′−y′)x′) copies of G−. This paragraph asserts, without proof, that the copies preserve the normalized prediction errors and that any solution meeting the bound '(1+x+y−ε)·OPT' must contain a vertex cover of size <(1−δ)n in some G+ or G− copy. To be a valid reduction one must prove with exact integer copy counts: (i) η+/OPT≤x and η−/OPT≤y for every Khot–Regev instance in the YES range; (ii) if every G+ and G− copy has cover size at least (1−δ)n, then the total cost strictly exceeds (1+x+y−ε)·OPT; and (iii) the boundary cases x=0 or y=0 are covered, since the stated copy counts are infinite there. The text gives no calculation, and the 'roughly/approximately' language obscures rounding errors of Θ(n) per extra copy, which can dominate the ε·OPT gap unless the constants are checked. The same gap transfers to Theorem 14. Since the abstract's optimality claim for the class depends on these lower bounds, the conditional acceptance should require this proof to be supplied.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":40,"tokens_out":14047,"duration_ms":190544,"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":[{"comment":"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.","section":"§5.2, final paragraph of the proof of Theorem 13; also §5.3, final paragraph of the proof of Theorem 14"},{"comment":"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.","section":"§5.2 and §5.3, first display of each lower-bound proof"}],"minor_comments":[{"comment":"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.","section":"§2, proof of Theorem 2"},{"comment":"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.","section":"§2, paragraph after Theorem 4"},{"comment":"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.","section":"§4.1, proof of Observation 8"},{"comment":"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.","section":"§6, \"Evaluation metrics\""},{"comment":"The maximization-ratio expression is printed as \"1 − (ρ−1) · η+ + η−/OPT\", which is ambiguous. It should be typeset with parentheses: 1 − ((ρ−1)η+ + η−)/OPT.","section":"§3 and abstract"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound results and the refined Steiner Tree analysis are strong and appear correct. The main doubt is whether the unweighted copy-count gadget in Section 5 can be repaired; if it cannot be made rigorous, the class-level optimality claim should be weakened to the weighted setting or stated only for the specific upper bounds, rather than as an optimality theorem. The UGC dependence is acceptable as long as it is stated as a conditional result. I would be happy to recommend acceptance after the lower-bound proof is supplied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the Antoniadis–Eliáš–Polak–Venzin paper on approximation algorithms with predictions. Short version: the main black-box results are correct and nicely presented, but the paper's headline optimality claim is currently built on a lower-bound proof that is a sketch, not a proof, and the class-wide statement should not be accepted as is.\n\nWhat is actually new: Theorem 2 is the clean observation that zeroing predicted weights and running any ρ-approximation gives additive error η+ + (ρ−1)η−; that is correct and gives a simple general tool. Theorem 4 for maximization is the right analogue, modulo a typo in the ratio direction ('at most' should be 'at least'). The refined Steiner Tree algorithm in Section 4 is the real work: the α-scaled Mehlhorn heuristic, the capping of η+ by (α−1) times the cost of a few MST edges, and the tight example are all coherent and add something beyond the black box. The experiments are honest and the code is available.\n\nThe soft spot is the lower-bound section. The weighted construction in Theorem 13 is fine as far as it goes, but the final paragraph that converts it to an unweighted instance says 'roughly' 1/(x′y′) copies and so on. That is load-bearing: the theorem is about Minimum Vertex Cover, i.e., unit weights, and the exact integer copy counts, the rounding errors, and the boundary cases x=0 or y=0 are not handled. The claim that any solution within (1+x+y−ε)·OPT must beat (1−δ)n in one copy needs a quantitative proof; rounding by one copy changes OPT by Θ(n), which can absorb the ε·OPT gap unless the constants are chosen carefully. The same gap transfers to Theorem 14 for Independent Set. This is probably fixable — the construction smells right — but as written it does not prove the stated theorems.\n\nMinor issues: the OPT formula in both lower-bound proofs uses x,y where it should use x′,y′; Theorem 4's 'at most' direction is wrong; and the normalized-cost formula in Section 6 has the denominator flipped (should be cMST − cOPT). None of these affect the main upper bounds.\n\nWho is this for: anyone working in algorithms with predictions will want the black-box tool and the Steiner Tree analysis. The paper deserves a serious referee: the gap is real but localized, and the core contribution is solid. I would send it out with a request to supply a rigorous version of the unweighted reduction before acceptance.","headline":"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.","tokens_in":24649,"tokens_out":9351,"would_cite":true,"duration_ms":84520,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Zeroing the weights of predicted items lets any approximation algorithm use predictions, with error-dependent guarantees and no slowdown.","keywords":["learning-augmented algorithms","approximation algorithms","combinatorial optimization","selection problems","prediction error","vertex cover","Steiner tree","Unique Games Conjecture"],"falsifier":"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.","tokens_in":23580,"feed_emoji":"🎯","tokens_out":10241,"duration_ms":84145,"temperature":0.7,"pith_summary":"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.","feed_headline":"Zeroing predicted weights upgrades any approximation algorithm","feed_subtitle":"Perfect predictions give optimal answers; prediction error degrades the guarantee smoothly and optimally.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the UGC-hard gap instances for Vertex Cover that the lower-bound theorems embed into the prediction-error parameters.","marker":"(Khot and Regev, 2008)"},{"why":"Provides the near-linear-time 2-approximation MST heuristic that the refined Steiner Tree algorithm scales and analyzes.","marker":"(Mehlhorn, 1988)"},{"why":"Introduces the MST heuristic whose structure the refined Steiner Tree algorithm inherits.","marker":"(Kou et al., 1981)"},{"why":"Gives the linear-time 2-approximation for weighted Vertex Cover used in examples and as the complementary problem for Independent Set and Clique.","marker":"(Bar-Yehuda and Even, 1981)"},{"why":"Provides the 2-approximation for V-join and the shortcutting argument that carries the Min-Weight Perfect Matching example.","marker":"(Goemans and Williamson, 1995)"},{"why":"Supplies the Euler-tour and matroid-exchange theorems used to bound the cost of connections in the refined Steiner Tree analysis.","marker":"(Korte and Vygen, 2012)"}],"fun_headline_variants":["Perfect predictions turn any approximation algorithm exact","Weight-subsidy method: predictions improve every selection problem","Error-scaled approximation: optimal when predictions are perfect","Predictions boost approximation ratios without extra runtime","Tight prediction bounds: from rho-approx to exact"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Perfect predictions turn any approximation algorithm exact","Weight-subsidy method: predictions improve every selection problem","Error-scaled approximation: optimal when predictions are perfect","Predictions boost approximation ratios without extra runtime","Tight prediction bounds: from rho-approx to exact"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00093,"raw_usage":{"total_tokens":3997,"prompt_tokens":976,"completion_tokens":3021,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":2956}},"tokens_in":592,"tokens_out":3021,"duration_ms":23380,"temperature":1.0,"reasoning_tokens":2956,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:58:18.511444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A faster approximation algorithm for the S teiner problem in graphs","cited_arxiv_id":null,"evidence_quote":"Provides the near-linear-time 2-approximation MST heuristic that the refined Steiner Tree algorithm scales and analyzes."}],"review_version":1}