Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.00220 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914523959525376 |
|---|---|
| author | Li, Jeffery Lynch, Jayson Olina, Liva Chen, Cecilia Lucas, Andrew Thompson, Neil |
| author_facet | Li, Jeffery Lynch, Jayson Olina, Liva Chen, Cecilia Lucas, Andrew Thompson, Neil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00220 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Impact of Approximation on Algorithmic Progress Li, Jeffery Lynch, Jayson Olina, Liva Chen, Cecilia Lucas, Andrew Thompson, Neil Data Structures and Algorithms 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. |
| title | The Impact of Approximation on Algorithmic Progress |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.00220 |