Improved Approximations for Hard Graph Problems using Predictions

Anders Aamand; Hao Wu; Justin Y. Chen; Sandeep Silwal; Siddharth Gollapudi

REVIEW 3 major objections 5 minor 1 cited by

Improved Approximations for Hard Graph Problems using Predictions

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Edge predictions that are barely better than random beat classical approximation barriers for four NP-hard graph problems.

desk verdict Edge predictions break real approximation barriers for VC/MIS/MaxCut; the set cover section has a fixable-looking proof gap that needs a corrected bound before publication. read the letter →

arxiv 2505.23967 v1 pith:X5T27GWF submitted 2025-05-29 cs.LG cs.DS

Anders Aamand , Justin Y. Chen , Siddharth Gollapudi , Sandeep Silwal , Hao Wu This is my paper · ORCID

classification cs.LGcs.DS MSC 68W2568R1090C27

keywords algorithmswithpredictionsedgelearning-augmentedapproximationvertexcoversetmaximumindependentmaxcut

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 tries to establish that a surprisingly weak kind of advice—one independent bit per edge per endpoint, each correct with probability $1/2+\varepsilon$ against a fixed optimal solution—suffices to outrun classical inapproximability results for four central NP-hard graph problems. If the theorems are right, polynomial-time algorithms can approximate Vertex Cover within $2-\Omega(\log\log(1/\varepsilon)/\log(1/\varepsilon))$, Set Cover within a constant that depends only on $\varepsilon$ rather than on $n$, Maximum Independent Set within $\Omega(\varepsilon^2/\log\log(1/\varepsilon))$, and MaxCut within $\alpha_{GW}+\tilde{\Omega}(\varepsilon^2)$. The unifying mechanism is that high-degree vertices receive many bits, so a majority vote is exponentially accurate, while the remaining bounded-degree graph can be handled by known specialized algorithms; careful charging arguments keep false positives and false negatives from ruining the ratios.

What carries the argument

The load-bearing machinery is a degree-threshold decomposition around $\Delta=100\log(1/\varepsilon)/\varepsilon^2$. Every vertex of degree at least $\Delta$ is classified by the majority of its incident prediction bits; a standard tail bound on sums of independent Bernoulli variables gives an error probability at most $\exp(-2\,\deg(v)\,\varepsilon^2)$, which is polynomially small in $\varepsilon$ at the threshold. These high-degree decisions cover the heavy-heavy and heavy-light edges, and the surviving low-degree graph, of maximum degree below $\Delta$, is then approximated by known bounded-degree algorithms: the $(2-2\log\log\Delta/\log\Delta)$ vertex cover algorithm, the $\Omega(\log\Delta/(\Delta\log\log\Delta))$-factor independent set algorithm, or the $(1+\ln\Delta)$ set cover algorithm. The proofs additionally use charging arguments that, for example, charge each false-positive high-degree vertex to a neighboring true optimal vertex, with each charge shown to be low-probability, so the added cost is absorbed by $\varepsilon^{O(1)}\mathrm{OPT}$.

What would settle it

Take a star (or a disjoint union of high-degree cliques), pick any optimal cover, and generate prediction bits that each have marginal accuracy $1/2+\varepsilon$ but are positively correlated across the edges incident to the center. The paper's concentration argument predicts each high-degree vertex is misclassified with probability at most $\exp(-2\,\deg(v)\,\varepsilon^2)$; correlated bits should make that probability constant, so the vertex cover ratio should fail to drop below $2-\Omega(\log\log(1/\varepsilon)/\log(1/\varepsilon))$. Observing that failure would show the independence assumption, not the marginal accuracy, is what carries the improvement.

Watch

Extended reading notes

Core claim

The central discovery is that edge predictions are strictly more useful than vertex predictions for edge-constrained objectives, even when each predicted bit is only $\varepsilon$-correlated with the truth. The paper proves: Theorem 4.1 gives an expected Vertex Cover approximation ratio of $2-\Omega(\log\log(1/\varepsilon)/\log(1/\varepsilon))$; Theorem A.1 extends this to weighted Vertex Cover; Theorem B.2 gives Set Cover ratio $1+\varepsilon^{10}+\ln\Delta$ with $\Delta=100\ln(1/\varepsilon)/\varepsilon^2$, hence a constant for fixed $\varepsilon$; Theorem 5.4 gives an $\Omega(\varepsilon^2/\log\log(1/\varepsilon))$ approximation for Maximum Independent Set; and Theorem C.2 gives a MaxCut ratio of $\alpha_{GW}+\tilde{\Omega}(\varepsilon^2)$. Because the classical counterparts of these bounds are tight under $\mathrm{P}\ne\mathrm{NP}$ or the Unique Games Conjecture, the paper's claim is that per-edge noisy advice moves these problems into an easier regime, not merely that the constants are improved.

Load-bearing premise

The argument's foundation is that every edge supplies two independent prediction bits, each correct with probability $1/2+\varepsilon$ against one fixed optimal solution; if the bits are correlated across edges, missing on some edges, or chosen adversarially within the $\varepsilon$ budget, the majority-vote concentration and charging arguments do not go through.

Editorial extensions

If this is right

For any fixed $\varepsilon>0$, Vertex Cover and Weighted Vertex Cover get randomized polynomial-time algorithms whose expected ratios are below 2, a guarantee that is impossible without advice unless the Unique Games Conjecture fails.
Set Cover is approximated within a constant depending only on $\varepsilon$, breaking the logarithmic lower bound that holds when $\mathrm{P}\ne\mathrm{NP}$ without predictions.
Maximum Independent Set, which is $n^{1-o(1)}$-hard to approximate in general, is approximated within $\Omega(\varepsilon^2/\log\log(1/\varepsilon))$ by a polynomial-time algorithm using these edge predictions.
MaxCut is approximated within $\alpha_{GW}+\tilde{\Omega}(\varepsilon^2)$, beating the standard SDP bound by an amount quadratic in the prediction advantage.
The same high-degree/low-degree recipe is reused across all four problems, so the results act as a general technique for edge-constrained NP-hard optimization rather than four isolated algorithms.

Reading between the lines

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

The paper does not discuss where the predictions come from; a natural extension is that a link classifier trained on past instances and emitting per-edge probabilities would realize the model, connecting noisy machine-learned advice directly to stronger approximation guarantees on future inputs.
Every edge must supply advice. Testing the algorithm with predictions sampled on only a subset of each vertex's incident edges would show whether the majority-vote concentration survives under partial advice, which the paper's theorems do not cover.
The vertex-cover proof already notes that 4-wise independence of the bits suffices; if the same weakening holds for set cover, maximum independent set, and max cut, the model would tolerate structured noise far beyond the i.i.d. assumption.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Let me give you the short version: this paper deserves a real referee, but the set cover section has a proof gap that the authors need to fix.

What's new is the prediction model: every edge gives two bits, one for each endpoint, each correct with probability 1/2 + ε. That small change from vertex predictions buys real barrier-breaking results—vertex cover below 2, a constant set cover factor for fixed ε, an Ω(ε^2 / loglog(1/ε)) independent set, and α_GW + Ω~(ε^2) max cut. The high-degree/low-degree decomposition is a clean unifying template, and the VC/MIS analyses look careful. The max cut section is a coherent extension of Ghoshal et al.; I didn't find a hole there. The experiments are small but honest.

The soft spot is exactly where the reader put it: Lemma B.7. For j ∈ J* with b_j = 1, the algorithm may skip j because S_j is already covered by earlier selected sets. The proof argues that then J_learned \ J* is nonempty, picks some j' in that set, and bounds Pr[j skipped] by Pr[b_{j'} = 1]. That is not a valid marginal bound: j' is chosen after the outcome, so you have to union-bound over all candidate false positives. That gives an n factor, which kills the claimed exp(-2|S_j|ε^2). Since Lemmas B.3–B.6 all lean on B.7, Theorem B.2 isn't established as written. I agree with the stress-test note that this is internal to the proof, not a disagreement with the model. It also looks fixable—maybe charge the miss to the uncovered element that forced the skip—but it needs actual work, not a footnote.

One smaller thing: in Eq. (1) of the MIS proof, the -2ε·α(G) is looser than the -ε·α(G) the argument gives. That's harmless and doesn't affect the theorem.

The model's full i.i.d. assumption across all edges is strong, but it's explicit and standard for this area, and the paper even notes 4-wise independence suffices for VC. I don't see circularity or fitted parameters.

Bottom line: send it to peer review. The VC, WVC, MIS, and MaxCut results are worth refereeing, and the set cover gap is specific enough that a competent referee can check whether a fix works. I'd cite this for the edge-prediction model and the VC/MIS results once the set cover issue is resolved.

Referee Report

3 major / 5 minor

Summary. The paper studies learning-augmented approximation algorithms for Vertex Cover, Weighted Vertex Cover, Set Cover, Maximum Independent Set, and MaxCut. It introduces an edge-based prediction model in which every edge independently provides one bit per endpoint, each bit agreeing with a fixed optimal solution with probability 1/2 + epsilon. The proposed algorithms follow a unified high/low-degree framework: majority votes over incident prediction bits are used for high-degree vertices, and classical bounded-degree or residual solvers are used for the remaining low-degree graph. The headline claimed results are a Vertex Cover ratio of 2 - Omega(log log(1/epsilon)/log(1/epsilon)), a Set Cover ratio of 1 + epsilon^10 + ln Delta with Delta = Theta(epsilon^{-2} log(1/epsilon)), an Independent Set ratio of Omega(epsilon^2 / log log(1/epsilon)), and a MaxCut ratio of alpha_GW + Omega_tilde(epsilon^2). An experimental section reports results for the MIS algorithm on three small real-world networks.

Significance. If fully established, these results would be significant: they show that weakly epsilon-correlated edge bits can break several classical approximation barriers in a clean, quantitative way, and the unifying high/low-degree framework is a useful conceptual contribution. The Vertex Cover, Weighted Vertex Cover, and MIS analyses are substantially worked out and appear internally coherent, including careful charging arguments for false positives and false negatives. The paper also gives a fair comparison with earlier vertex-prediction models and clearly identifies the new difficulties introduced by edge constraints. However, the Set Cover and MaxCut guarantees currently rest on gaps in the appendix proofs. In particular, the key probabilistic lemma for Set Cover is not proved as written, and a central inequality in the MaxCut analysis has the wrong direction for low-degree neighbors of wide vertices. The significance of the paper is therefore conditional on repairing these two appendix analyses.

major comments (3)

[Appendix B, Lemma B.7] Lemma B.7 is not established as written. In the false-negative case j in J* with b_j = 1 and j skipped because S_j is already covered by previously selected sets, the proof chooses an index j' in J_learned \ J* after the random outcome and bounds the event by Pr[b_{j'} = 1]. Since j' is a data-dependent index, Hoeffding's inequality cannot be applied to that particular j'; a union bound over all possible candidate sets j' of size at least |S_j| introduces a factor at least n, which is not present in the claimed bound. Lemmas B.3, B.5, and B.6 all rely on Lemma B.7, so Theorem B.2 is not proved. A correct argument would need to reason about the entire minimal subcollection of false positives that covers S_j, rather than marginalizing over one post-hoc chosen element of it.
[Appendix B, proof of Theorem B.2] The derivation of the bound on |J_fix| is missing. Lemma B.6 bounds E[|U_fix|], the number of uncovered elements, but J_fix is a (ln m)-approximate Set Cover on U_fix, so |J_fix| <= (ln m) * OPT_fix, and OPT_fix can be as large as |U_fix| (e.g., via singleton sets). The displayed chain in the proof of Theorem B.2 replaces |J_fix| directly by epsilon^10 * |J*_>=Delta|, which does not follow from Lemma B.6. As written, one would only obtain an extra factor of ln m, which is not bounded by a function of epsilon alone. Even after repairing Lemma B.7, the m-dependence of J_fix must be controlled explicitly before the claimed (1 + epsilon^10 + ln Delta)|J*| bound is valid.
[Appendix C, Lemma C.10] The proof of Lemma C.10 uses the inequality sqrt(sum_j tilde A_{i,j}^2 / deg(j)) <= sqrt(sum_j tilde A_{i,j}^2 / Delta) for every (Delta, eta)-wide vertex i. This is only valid if every j with tilde A_{i,j} > 0 satisfies deg(j) >= Delta. But a wide graph may contain wide vertices adjacent to narrow vertices of small degree; in particular, all degree-1 vertices are narrow, and the wide-graph condition only bounds the total weighted degree of narrow vertices by eta W. For such neighbors, 1/deg(j) > 1/Delta, so the inequality has the wrong direction. Concretely, a wide center with Theta(Delta) degree-1 narrow leaves of edge weight about eta W_c / Delta contributes Theta(eta W_c / (epsilon sqrt(Delta))) to Err, which exceeds the claimed per-vertex bound sqrt(eta) W_c / Delta by a factor polynomial in 1/epsilon when Delta = Theta(1/epsilon). Lemma C.10, and therefore Theorem C.7 and Theorem C.2, are not established as stated; a fix would need to truncate or separately charge the contribution of edges incident to narrow low-degree vertices.

minor comments (5)

[Section 6, experimental setup] The reported experiments fix the degree threshold at 10 or 15, whereas Algorithm 2 specifies Delta = 3 log(1/epsilon)/epsilon^2; for example, at epsilon = 0.1 the theoretical threshold is about 690. The experiments therefore do not faithfully instantiate the analyzed algorithm over the reported epsilon range.
[Figure 2 caption] The caption says 'learning-augmented frequency estimation algorithms', but the figure plots Maximum Independent Set approximation ratios; the wording should be corrected.
[Appendix B, proof of Theorem B.2] The sentence 'Bounding the second term with Theorem B.4' refers to the false-positive term |J_learned \ J*_>=Delta|; the correct reference is Lemma B.3.
[Throughout appendices] Several lemmas are referred to as 'Theorem' (for example, 'Theorem E.1', 'Proving Theorems A.5 to A.9', and 'Theorem 4.3' in Section 4). This inconsistent numbering and naming makes cross-referencing unnecessarily difficult.
[Section 5, proof of Theorem 5.4] The step 'using the fact that e^x >= 2x' and the following two displayed lines are terse; expanding the algebra would help the reader verify the intended bound Pr[X_v = 1] <= epsilon/(2d_v).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: predictions are exogenous inputs, algorithms use external classical approximation results, and thresholds are analytic in epsilon.

full rationale

Walking the derivation chain, the load-bearing steps are: (i) Definition 1.1 supplies i.i.d. bits correlated with a fixed optimal solution; (ii) majority-vote concentration (Lemma E.1, Lemma B.7) converts the i.i.d. assumption into per-vertex error exp(-2 d_v epsilon^2); (iii) charging arguments bound false positives and false negatives against OPT; and (iv) classical algorithms (Halperin 2002, Halldorsson 1998, Lovasz 1975, Cohen-Addad et al. 2024 Proposition C.6) are applied to the remaining low-degree or narrow subgraphs. None of these steps fits a parameter to the claimed output and then reports that output as a prediction: the prediction bits are inputs, thresholds such as Delta = 100 log(1/epsilon)/epsilon^2 are analytic functions of epsilon, and no uniqueness or ansatz is imported from work by the same authors. The few self-citations (Chen-Silwal et al. 2022a,b; Ergun et al.) appear in introductory or related-work comments and are not load-bearing. The only flagged issue, the post-hoc choice of j' in Lemma B.7, is a possible probabilistic correctness gap in the Set Cover proof, not a circular reduction of the theorem to its own inputs, so it does not affect the circularity score. Verdict: no significant circularity.

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

The central claims rely on standard concentration inequalities, classical bounded-degree approximation algorithms (Halperin 2002, Halldorsson 1998), the cited max cut proposition of Cohen-Addad et al., and the i.i.d. edge-prediction model. Thresholds are analytic functions of epsilon. The only hand-picked numbers are experimental degree cutoffs and the unspecified small constants eta and c in the max cut section. No new physical or mathematical entities are postulated.

free parameters (4)

Delta (VC/WVC/Set Cover threshold) = 100 log(1/epsilon)/epsilon^2
Analytic threshold, not fitted to data; chosen so majority error probability is about epsilon^200.
Delta (MIS threshold) = 3 log(1/epsilon)/epsilon^2
Analytic threshold; chosen so exp(-2 Delta epsilon^2) <= epsilon^6.
eta and c (MaxCut universal constants)
Existentially chosen small constants in Theorem C.2 and Remark C.8; no data fitting.
Experimental degree thresholds = 10 (facebook, twitch), 15 (congress)
Hand-picked in Section 6 experiments; not tied to the theoretical threshold and not load-bearing.

assumptions (7)

domain assumption Prediction bits are i.i.d. across edges and endpoints, each correct with probability 1/2+epsilon.
Definition 1.1 and its analogues; this enables Hoeffding concentration for majority votes.
standard math Hoeffding's inequality applies to the majority vote sums.
Used throughout Sections 4, 5, B, and C to bound majority-vote error probabilities.
domain assumption Halperin's (2 - 2 log log Delta/log Delta)-approximation for vertex cover on graphs of maximum degree Delta exists and is polynomial time.
Invoked in Algorithm 1 line 15 and Algorithm 3 line 24, cited to Halperin 2002.
domain assumption Halldorsson's Omega(log Delta/(Delta log log Delta))-approximation for MIS on graphs of maximum degree Delta exists.
Theorem 5.1, used in Algorithm 2 line 4.
standard math Caro-Wei bound alpha(G) >= sum 1/(1+d_v).
Lemma 5.3, used to bound expected bad votes in the MIS analysis.
domain assumption Cohen-Addad et al. Proposition C.6: (Delta,eta)-narrow graphs admit alpha_GW + Omega_tilde(eta^5/Delta^2) max cut approximation.
Cited external result used in Theorem C.2 for narrow graphs.
standard math A minimum vertex cover or set cover is inclusion-wise minimal.
Used in Lemma 4.4(2) and Lemma B.7 to argue each optimal vertex or set has a witness not covered by the rest of the optimal solution.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Improved Approximations for Hard Graph Problems using Predictions." pith.science (2026). https://pith.science/paper/X5T27GWF

@misc{pith2026250523967,
  author       = {Pith},
  title        = {Pith review of: Improved Approximations for Hard Graph Problems using Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X5T27GWF}},
  note         = {Machine review of arXiv:2505.23967}
}

abstract

We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.

Figures

Figures reproduced from arXiv: 2505.23967 by the authors.

**Figure 1.** A high-level description of the underlying structure common among our algorithms. the Independent Set problem, an edge may be adjacent to both low-degree and high-degree vertices, and both steps (lines 2 and 4) may select both endpoints which would violate the constraints of the problem. We refer to the individual problem sections for more details. To complement our theoretical results, we also experimentally test… view at source ↗

**Figure 2.** Comparison of learning-augmented frequency estimation algorithms. Top: congress, Middle: facebook, Bottom: twitch. The plots compare Algorithm 2 with the optimal solution, the standard greedy approximation of MIS, and a degree-agnostic “predictionsonly” heuristic. The algorithms are averaged across 10 trials. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
cs.LG 2026-07 accept novelty 7.0 of 10

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

Reference graph

Works this paper leans on

30 extracted references · 19 canonical work pages · cited by 1 Pith paper

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

Approximation algorithms for combinatorial optimization with predictions

Antoniadis, A., Eli \'a s , M., Polak, A., and Venzin, M. Approximation algorithms for combinatorial optimization with predictions. arXiv preprint arXiv:2411.16600, 2024

arXiv 2024
[3]

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

Bampis, E., Escoffier, B., and Xefteris, M. Parsimonious learning-augmented approximations for dense instances of np-hard problems. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=AD5QC1BTJL

work page 2024
[4]

Learning-augmented maximum independent set

Braverman, V., Dharangutte, P., Shah, V., and Wang, C. Learning-augmented maximum independent set. In Kumar, A. and Ron - Zewi, N. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK , volume 317 of LIPIcs, pp.\ 24:1--24:18. Schloss ...

doi:10.4230/lipics.approx/random.2024.24 2024
[5]

Faster fundamental graph algorithms via learned predictions

Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp.\ 3583--3602. PMLR, 2022 a

work page 2022
[6]

Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M

Chen, J. Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M. Triangle and four cycle counting with predictions in graph streams. In International Conference on Learning Representations, 2022 b . URL https://openreview.net/forum?id=8in_5gN9I0

work page 2022
[7]

A greedy heuristic for the set-covering problem

Chv \' a tal, V. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4 0 (3): 0 233--235, 1979. doi:10.1287/MOOR.4.3.233. URL https://doi.org/10.1287/moor.4.3.233

doi:10.1287/moor.4.3.233 1979
[8]

Learning-augmented approximation algorithms for maximum cut and related problems

Cohen-Addad, V., d'Orsi, T., Gupta, A., Lee, E., and Panigrahi, D. Learning-augmented approximation algorithms for maximum cut and related problems. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

work page 2024

Show all 30 references

[9]

CPLEX, I. I. V22.1: User’s manual for cplex. International Business Machines Corporation, 46 0 (53): 0 157, 2025

2025
[10]

and Steurer, D

Dinur, I. and Steurer, D. Analytical approach to parallel repetition. In Shmoys, D. B. (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 , pp.\ 624--633. ACM , 2014. doi:10.1145/2591796.2591884. URL https://doi.org/10.1145/2591796.2591884

2014
[11]

C., Feng, Z., Silwal, S., Woodruff, D., and Zhou, S

Ergun, J. C., Feng, Z., Silwal, S., Woodruff, D., and Zhou, S. Learning-augmented k -means clustering. In International Conference on Learning Representations
[12]

G., Fullin, K., Gutierrez, G., Omodt, N., Zinnecker, S., Sprint, G., and McCulloch, S

Fink, C. G., Fullin, K., Gutierrez, G., Omodt, N., Zinnecker, S., Sprint, G., and McCulloch, S. A centrality measure for quantifying spread on weighted, directed networks. Physica A, 2023

2023
[13]

Approximate cluster recovery from noisy labels

Gamlath, B., Lattanzi, S., Norouzi-Fard, A., and Svensson, O. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, pp.\ 1463--1509. PMLR, 2022

2022
[14]

Constraint satisfaction problems with advice

Ghoshal, S., Markarychev, K., and Markarychev, Y. Constraint satisfaction problems with advice. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 1202--1221. SIAM, 2025

2025
[15]

Goemans, M. X. and Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM , 42 0 (6): 0 1115--1145, 1995. doi:10.1145/227683.227684. URL https://doi.org/10.1145/227683.227684

1995
[16]

Halld \' o rsson, M. M. Approximations of independent sets in graphs. In Jansen, K. and Hochbaum, D. S. (eds.), Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings, volume 1444 of Lecture No...

1998 doi
[17]

Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

Halperin, E. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. , 31 0 (5): 0 1608--1623, 2002. doi:10.1137/S0097539700381097. URL https://doi.org/10.1137/S0097539700381097

2002 doi
[19]

Clique is hard to approximate within n$ ^ 1-epsilon $

H stad, J. Clique is hard to approximate within n$ ^ 1-epsilon $. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996 , pp.\ 627--636. IEEE Computer Society, 1996 b . doi:10.1109/SFCS.1996.548522. URL https://d...

1996
[20]

Learning-based frequency estimation algorithms

Hsu, C.-Y., Indyk, P., Katabi, D., and Vakilian, A. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019

2019
[21]

Jiang, T., Li, Y., Lin, H., Ruan, Y., and Woodruff, D. P. Learning-augmented data stream algorithms. ICLR, 2020

2020
[22]

Johnson, D. S. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9 0 (3): 0 256--278, 1974. doi:10.1016/S0022-0000(74)80044-9. URL https://doi.org/10.1016/S0022-0000(74)80044-9

1974 doi
[23]

and Regev, O

Khot, S. and Regev, O. Vertex cover might be hard to approximate to within 2- varepsilon. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark , pp.\ 379. IEEE Computer Society, 2003. doi:10.1109/CCC.2003.1214437. URL ht...

2003 arXiv
[24]

and Regev, O

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

2008
[25]

and Mcauley, J

Leskovec, J. and Mcauley, J. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012

2012
[26]

On the ratio of optimal integral and fractional covers

Lov \' a sz, L. On the ratio of optimal integral and fractional covers. Discret. Math., 13 0 (4): 0 383--390, 1975. doi:10.1016/0012-365X(75)90058-8. URL https://doi.org/10.1016/0012-365X(75)90058-8

1975 doi
[27]

and Vassilvitskii, S

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

2021
[28]

and Vassilvitskii, S

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

2022
[29]

and Sarkar, R

Rozemberczki, B. and Sarkar, R. Twitch gamers: a dataset for evaluating proximity preserving and structural role-based node embeddings, 2021

2021
[30]

Non-approximability results for optimization problems on bounded degree instances

Trevisan, L. Non-approximability results for optimization problems on bounded degree instances. In Vitter, J. S., Spirakis, P. G., and Yannakakis, M. (eds.), Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece , pp.\ 453--4...

2001
[31]

Williamson, D. P. and Shmoys, D. B. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0-521-19527-0. URL http://www.cambridge.org/de/knowledge/isbn/item5759340/?site\_locale=de\_DE

2011

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

Approximation algorithms for combinatorial optimization with predictions

Antoniadis, A., Eli \'a s , M., Polak, A., and Venzin, M. Approximation algorithms for combinatorial optimization with predictions. arXiv preprint arXiv:2411.16600, 2024

arXiv 2024

[3] [3]

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

Bampis, E., Escoffier, B., and Xefteris, M. Parsimonious learning-augmented approximations for dense instances of np-hard problems. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=AD5QC1BTJL

work page 2024

[4] [4]

Learning-augmented maximum independent set

Braverman, V., Dharangutte, P., Shah, V., and Wang, C. Learning-augmented maximum independent set. In Kumar, A. and Ron - Zewi, N. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK , volume 317 of LIPIcs, pp.\ 24:1--24:18. Schloss ...

doi:10.4230/lipics.approx/random.2024.24 2024

[5] [5]

Faster fundamental graph algorithms via learned predictions

Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp.\ 3583--3602. PMLR, 2022 a

work page 2022

[6] [6]

Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M

Chen, J. Y., Eden, T., Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D., and Zhang, M. Triangle and four cycle counting with predictions in graph streams. In International Conference on Learning Representations, 2022 b . URL https://openreview.net/forum?id=8in_5gN9I0

work page 2022

[7] [7]

A greedy heuristic for the set-covering problem

Chv \' a tal, V. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4 0 (3): 0 233--235, 1979. doi:10.1287/MOOR.4.3.233. URL https://doi.org/10.1287/moor.4.3.233

doi:10.1287/moor.4.3.233 1979

[8] [8]

Learning-augmented approximation algorithms for maximum cut and related problems

Cohen-Addad, V., d'Orsi, T., Gupta, A., Lee, E., and Panigrahi, D. Learning-augmented approximation algorithms for maximum cut and related problems. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

work page 2024