pith. sign in

arxiv: 2605.00220 · v1 · submitted 2026-04-30 · 💻 cs.DS

The Impact of Approximation on Algorithmic Progress

Jeffery Li , Jayson Lynch , Liva Olina , Cecilia Chen , Andrew Lucas , Neil Thompson This is my paper

Pith reviewed 2026-05-09 19:34 UTC · model grok-4.3

classification 💻 cs.DS
keywords approximation algorithmsalgorithmic complexitycomputational problemstime complexityNP-hard problemslinear time algorithmssurveyintractable problems
0
0 comments X p. Extension

The pith

Approximation has benefited only about 20% of the most important algorithm problems but enables much faster computation for those that do.

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

This paper examines 118 key problems in computer science to assess the historical impact of allowing approximate solutions with small errors. It concludes that approximation has improved only roughly one fifth of these problems, yet for the benefiting cases it often reduces computation time from exponential to polynomial while keeping accuracy high. This matters because exact algorithms are frequently too slow for large instances in science and industry, so knowing where approximation works provides a practical way forward. The survey also reveals that approximation has increased the proportion of linear-time algorithms by 23 percent, which is especially useful for big data applications. Additionally, the authors connect these findings to progress in artificial intelligence, where approximation is central to deep learning.

Core claim

Through a systematic review of 118 canonical algorithm problems, the authors find that approximation has led to better algorithms for approximately 20% of them. Among computationally intractable problems, a quarter now admit polynomial-time approximate algorithms. This approach has also expanded the set of problems solvable in linear time by 23%. The gains typically involve only minor sacrifices in solution quality, offering a valuable alternative when exact methods are infeasible due to time constraints.

What carries the argument

A classification of the 118 problems based on whether they possess good approximate algorithms that improve time complexity compared to exact versions, along with quantitative tracking of complexity class shifts.

Load-bearing premise

The chosen set of 118 problems is representative of the most significant algorithm problems, and the determination of which ones have benefited from approximation is consistent and without bias.

What would settle it

Repeating the survey with a different but equally authoritative set of 118 problems and obtaining a markedly different percentage of problems that benefited from approximation would challenge the result.

Figures

Figures reproduced from arXiv: 2605.00220 by Andrew Lucas, Cecilia Chen, Jayson Lynch, Jeffery Li, Liva Olina, Neil Thompson.

Figure 1
Figure 1. Figure 1: Historical progress and current state of approximation algorithms. 2020s estimates assume that future years values will (proportionally) follow a trajectory similar to the 2010s. the 1970s, around 8-12% of the algorithm problems in our dataset see these improvements. In total, approximation algorithms have provided significant asymptotic runtime improvements for around one-fifth of the algorithm problems i… view at source ↗
Figure 2
Figure 2. Figure 2: Theoretical improvements and characteristics (arbitrarily closeness, types of error) of approximation algorithms. For (a), faded dots indicate algorithms that do not improve the best runtime. Dots and lines between tick marks represent intermediate values. These plots are more specifically for Undirected, Unweighted All-Pairs Shortest Paths, and for the Geometric Traveling Salesman Problem. 5 [PITH_FULL_I… view at source ↗
Figure 3
Figure 3. Figure 3: Relative improvements over time for three different problems (All-Pairs Shortest Paths, Traveling Salesman Problem, and Set Cover Problem) at three different levels of error, using prob￾lem size n = 106 . problems see small improvements due to slight improvements to the polynomial exponent in the runtime, that occasionally get matched by later improvements from exact algorithms. On the other hand, we have … view at source ↗
Figure 4
Figure 4. Figure 4: Distributions of the annualized improvements the best approximation algorithms achieve over the best exact algorithms, measured from the year of the first algorithm for each problem, across different problem sizes (n) and error tolerances (the answer returned by the algorithm is within this additive term or multiplicative factor of the optimal). 9 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
read the original abstract

In nearly every discipline, scientific computations are limited by the cost and speed of computation. For example, the best-known exact algorithms for the canonical Traveling Salesman Problem would take centuries to run on an instance of size 1 million. A natural response to such limits is to try to find new algorithms or to parallelize existing ones, but many algorithms are already at their theoretically-optimal level and parallelization is often impossible or prohibitively expensive. Starting in the 1960's, computer scientists pursued another solution: allowing solutions to have a small amount of error (i.e. approximating them). In this paper, we survey 118 of the most important algorithm problems in computer science, quantifying the gains and tradeoffs from approximation that have been discovered over the history of the field. Overall, only $\approx$20\% of problems have benefited from approximation. However, those with good approximate algorithms can be dramatically faster to compute with little cost to accuracy. For example, a quarter of computationally intractable problems (e.g. those that take exponential time to compute) have polynomial time approximate algorithms. Approximation also increases the number of algorithms that can run in linear time by 23\%, opening up new computational opportunities for those working in the big data regime. This work also sheds light on what should be expected from progress in AI, where approximation is at the heart of how deep learning works.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper surveys 118 important algorithm problems and quantifies the historical impact of approximation algorithms, claiming that only ≈20% have benefited, that a quarter of intractable problems gain polynomial-time approximations, and that approximation increases the number of linear-time algorithms by 23%.

Significance. If the underlying classification of problems and complexity improvements is reproducible and unbiased, the work offers a rare quantitative view of approximation's contribution to algorithmic progress, with potential implications for expectations around AI-driven approximations. The survey approach itself has no free parameters or self-referential derivations.

major comments (3)
  1. [Abstract and §2] The selection procedure, source list, and sampling criteria for the 118 problems are not described (abstract and §2), so it is impossible to assess whether the set is representative or whether the ≈20% 'benefited' figure is robust to different choices of 'most important' problems.
  2. [Abstract and §3] No explicit decision rule is supplied for classifying a problem as having 'benefited from approximation' (e.g., any constant-factor approximation, only PTAS/FPTAS, or specific complexity-class improvement). This definition is load-bearing for every headline percentage.
  3. [§4 and §5] The before/after complexity pairs used to compute the 'quarter of intractable problems gain poly-time approx' and '+23% linear-time algorithms' statistics are not tabulated or referenced, preventing verification or sensitivity analysis of these derived claims.
minor comments (2)
  1. [Abstract] The abstract states headline numbers without error bars or confidence intervals; adding these (or a sensitivity table) would improve clarity even if the underlying data remain the same.
  2. [§2] Notation for complexity classes and approximation ratios is introduced without a dedicated glossary or table, which may hinder readers outside the core algorithms community.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments correctly identify gaps in documentation that affect reproducibility and verifiability. We will revise the manuscript to supply the missing details on problem selection, classification rules, and supporting data. Our point-by-point responses follow.

read point-by-point responses

  1. Referee: [Abstract and §2] The selection procedure, source list, and sampling criteria for the 118 problems are not described (abstract and §2), so it is impossible to assess whether the set is representative or whether the ≈20% 'benefited' figure is robust to different choices of 'most important' problems.

    Authors: We agree that the selection procedure must be described explicitly. The current manuscript does not detail the sources or criteria used to compile the 118 problems. In the revised version we will expand §2 with a complete account of the source lists (standard references such as Garey & Johnson and major algorithmic surveys), the definition of 'important' problems, and the inclusion/sampling rules. This will permit readers to judge representativeness and test robustness of the ≈20% statistic under alternative selections. revision: yes

  2. Referee: [Abstract and §3] No explicit decision rule is supplied for classifying a problem as having 'benefited from approximation' (e.g., any constant-factor approximation, only PTAS/FPTAS, or specific complexity-class improvement). This definition is load-bearing for every headline percentage.

    Authors: We accept that an explicit decision rule is required. The manuscript applies an implicit classification without stating the precise criteria. We will add a dedicated paragraph in §3 that defines 'benefited from approximation' in operational terms (e.g., any constant-factor guarantee, PTAS/FPTAS, or measurable improvement in complexity class) and explains how each problem was evaluated against this rule. The revised text will make every headline percentage directly traceable to this definition. revision: yes

  3. Referee: [§4 and §5] The before/after complexity pairs used to compute the 'quarter of intractable problems gain poly-time approx' and '+23% linear-time algorithms' statistics are not tabulated or referenced, preventing verification or sensitivity analysis of these derived claims.

    Authors: We agree that the underlying pairs must be presented for verification. The manuscript derives the quarter and +23% figures from these pairs but does not tabulate or cite them. In the revision we will insert a table (or supplementary table referenced in §§4–5) that lists the relevant before-and-after complexity classes for the contributing problems, together with citations to the original papers. This will enable independent checks and sensitivity analyses. revision: yes

Circularity Check

0 steps flagged

No circularity: survey aggregates external results without self-referential reduction

full rationale

The paper presents a survey of 118 algorithm problems drawn from external literature, with headline percentages (≈20% benefited from approximation, 25% of intractable problems gaining polynomial-time approximations, +23% linear-time algorithms) obtained by direct classification and counting. No equations, fitted parameters, predictions, or first-principles derivations exist that could reduce to the inputs by construction. The selection and classification steps are not self-definitional or load-bearing self-citations; they are aggregations of independent prior results. The derivation chain is therefore self-contained against external benchmarks and exhibits no circularity of any enumerated kind.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claims rest entirely on the authors' curation and classification of 118 problems plus their historical assessment of approximation benefits; none of these steps are independently verifiable from the abstract. No free parameters, axioms, or invented entities are introduced.

pith-pipeline@v0.9.0 · 5550 in / 1286 out tokens · 59243 ms · 2026-05-09T19:34:14.268115+00:00 · methodology

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

18 extracted references · 2 canonical work pages

  1. [1]

    E. Liu. A Metastudy of Algorithm Lower Bounds.Master’s thesis, Massachusetts Institute of Technology, 2021

    2021

  2. [2]

    E. Liu, Y. Sherry, W. Kuszmaul, J. Lynch, and N. C. Thompson. How Close are Algorithms to being Optimal?Working Paper, 2023

    2023

  3. [3]

    D. Tontici. Progress in Parallel Algorithms.Master’s thesis, Massachusetts Institute of Technology, 2024

    2024

  4. [4]

    W. J. Cook.In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2015

    2015

  5. [5]

    Hartmanis and R

    J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms.Trans- actions of the American Mathematical Society, 117:285–306, 1965

    1965

  6. [6]

    C. E. Leiserson, N. C. Thompson, J. S. Emer, B. C. Kuszmaul, B. W. Lampson, D. Sanchez, and T. B. Schardl. There’s plenty of room at the Top: What will drive computer performance after Moore’s law?Science, 368(6495):eaam9744, 2020

    2020

  7. [7]

    Sherry and N

    Y. Sherry and N. C. Thompson. How Fast do Algorithms Improve? [Point of View]. Proceedings of the IEEE, 109(11):1768–1777, 2021

    2021

  8. [8]

    H. Rome. The Space Race: Progress in Algorithm Space Complexity.Master’s thesis, Massachusetts Institute of Technology, 2023

    2023

  9. [9]

    H. Rome, J. Lynch, J. Li, C. Falor, and N. C. Thompson. How Fast are Algorithms Re- ducing the Demands on Memory? A Survey of Progress in Space Complexity.Working Paper, 2024

    2024

  10. [10]

    Srinivasan

    A. Srinivasan. Approximation algorithms via randomized rounding: a survey.Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, pages 9–71, 1999

    1999

  11. [11]

    Motwani and P

    R. Motwani and P. Raghavan.Randomized Algorithms.Cambridge University Press, 1995

    1995

  12. [12]

    V. V. Vazirani.Approximation Algorithms, volume 1. Springer, Berlin, 2001

    2001

  13. [13]

    D. P. Williamson and D. B. Shmoys.The Design of Approximation Algorithms. Cam- bridge university press, 2011

    2011

  14. [14]

    F. L. Gall. Faster Algorithms for Rectangular Matrix Multiplication.CoRR, abs/1204.1111, 2012

    work page arXiv 2012

  15. [15]

    Aingworth, C

    D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication).SIAM Journal on Computing, 14 The Impact of Approximation on Algorithmic Progress Jeffery Li, et al. 28(4):1167–1181, 1999

    1999

  16. [16]

    Baswana, V

    S. Baswana, V. Goyal, and S. Sen. All-pairs nearly 2-approximate shortest paths in o(n2 polylogn) time.Theoretical Computer Science, 410(1):84–93, 2009

    2009

  17. [17]

    Dinur and D

    I. Dinur and D. Steurer. Analytical Approach to Parallel Repetition.CoRR, abs/1305.1979, 2013

    work page arXiv 1979

  18. [18]

    Hornik, M

    K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are uni- versal approximators.Neural networks, 2(5):359–366, 1989. 15

    1989