# Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems

arXiv: https://arxiv.org/abs/2402.02062 · HTML: https://mlsanity.com/paper/2402.02062/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2024.

## Built on by (most cited first, 7 of 7)

- [Improved Approximations for Hard Graph Problems using Predictions](https://mlsanity.com/paper/2505.23967/) (2025)
- [Learning-Augmented Algorithms for Boolean Satisfiability](https://mlsanity.com/paper/2505.06146/) (2025)
- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)
- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)
- [Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling](https://mlsanity.com/paper/2606.13133/) (2026)
- [Learning Augmented Exact Exponential Algorithms](https://mlsanity.com/paper/2606.18807/) (2026)
- [Compressing Value Predictions for Learning-Augmented Metrical Task Systems](https://mlsanity.com/paper/2609.33580/) (2026)

## Abstract (arXiv)

The classical work of (Arora et al., 1999) provides a scheme that gives, for any ε>0, a polynomial time 1-ε approximation algorithm for dense instances of a family of NP-hard problems, such as Max-CUT and Max-k-SAT. In this paper we extend and speed up this scheme using a logarithmic number of one-bit predictions. We propose a learning augmented framework which aims at finding fast algorithms which guarantees approximation consistency, smoothness and robustness with respect to the prediction error. We provide such algorithms, which moreover use predictions parsimoniously, for dense instances of various optimization problems.