<p>I am not aware of a general theory being developed on approximation algorithms for problems in P. I know of a particular problem, though, that is called approximate distance oracles:</p>

<blockquote>
  <p>Given a weighted undirected graph $G = (V, E)$ with $n = |V|$ nodes and $m = |E|$ edges, a point-to-point query asks for the distance between two nodes $s, t \in V$. </p>
</blockquote>

<p>There is a three-way trade-off between space, query time and approximation in the distance oracle problem. One can trivially answer each query exactly (approximation = $1$) in $O(1)$ time by storing the all-pair distance matrix; or in $O(m + n\log n)$ time by running a shortest path algorithm. For massive graphs, these two solutions may require prohibitively large space (to store the matrix) or query time (to run a shortest path algorithm). Hence, we allow approximation.</p>

<p>For general graphs, the state-of-the-art is the <a href="http://www.cs.tau.ac.il/~zwick/papers/oracle-JACM-revision.ps">distance oracle of Thorup and Zwick</a>, which for any given approximation $k$, requires optimal space. It also gives you a nice space-approximation trade-off.</p>

<p>For sparse graphs, a more general space-approximation-time trade-off can be <a href="http://www.cs.illinois.edu/homes/agarwa16/pubs/ismp2012.pdf">shown</a>.</p>

CC BY-SA 3.0
2012-03-28T01:26:26.760Z
2012-03-28T01:26:26.760Z
Rachit
<p>We often seek approximate solutions to simple problems like finding shortest path in a graph, finding number of unique elements in a set. The constraint here is that the input is large and we want to solve the problem approximately using a single pass over the data. There are several "streaming" algorithms designed to achieve approximate solutions in linear/near-linear time.</p>

<p>One problem I worked on, is <a href="http://dl.acm.org/citation.cfm?id=1777889">approximating betweenness centrality</a>. This can be solved in $O(nm)$ time on graphs with $n$ vertices and $m$ edges. A linear time algorithm giving a constant factor approximation to betweenness centrality is of very practical importance.</p>

CC BY-SA 3.0
2012-03-28T18:51:36.790Z
2012-03-28T19:38:08.047Z
2012-03-28T19:38:08.047Z
Shiva Kintali
<p>Non-exhaustive list of recent papers that find approximate solutions for problems in $P$</p>

<p>1) There is a great amount of work on approximate solutions for linear equations (symmetric diagonally dominant) in nearly linear time $\mathcal{O}(n\cdot\text{polylog}(n))$</p>

<p>(list of papers) <a href="http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html" rel="nofollow">http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html</a></p>

<p>(In general most iterative solvers for linear equations share the principle of $\epsilon$-approximating the true solution. The same goes for iterative methods that solve more general problems (e.g., some convex/linear programs)).</p>

<p>2) Approximate solutions to min/max $s-t$ cuts/flows
<a href="http://people.csail.mit.edu/madry/docs/maxflow.pdf" rel="nofollow">http://people.csail.mit.edu/madry/docs/maxflow.pdf</a></p>

<p>3) Finding a sparse approximation of the Fourier transform of a signal in sublinear time <a href="http://arxiv.org/pdf/1201.2501v1.pdf" rel="nofollow">http://arxiv.org/pdf/1201.2501v1.pdf</a></p>

<p>4) Finding the approximate principal component of a matrix <a href="http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf" rel="nofollow">http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf</a></p>

CC BY-SA 3.0
2012-03-28T13:46:05.667Z
2012-03-31T19:27:47.243Z
2012-03-31T19:27:47.243Z
Dimitris
<p>Fast approximation algorithms for maximum matching are known. Atleast one that that comes to my mind immediately is <a href="http://arxiv.org/pdf/1112.0790v1.pdf">http://arxiv.org/pdf/1112.0790v1.pdf</a>. </p>

CC BY-SA 3.0
2012-03-28T02:18:19.253Z
2012-03-28T02:18:19.253Z
Ashwinkumar B V
<p>Another reason that we will sometimes look for approximation algorithms for problems in $P$ is because there is some other (non-computational) constraint on our algorithm that precludes an exact solution. One example of such a constraint is <a href="http://en.wikipedia.org/wiki/Differential_privacy">differential privacy</a>: differentially private algorithms will necessarily return only approximate solutions. So in recent years, there has been effort to design approximation algorithms for problems that are otherwise easy to solve exactly: e.g. min-cut, low-rank matrix approximation, computing simple summations, etc. Some of these also happen to run more quickly than the exact solution would, but others have running time that is <em>much</em> slower than a non-private exact solution. </p>

CC BY-SA 3.0
2012-04-01T10:41:41.667Z
That's another great motivation for approximation. Thanks for pointing that out!
aelguindy
CC BY-SA 3.0
2012-03-29T16:07:50.230Z
2012-03-29T18:04:08.687Z
2012-03-29T18:04:08.687Z
Aaron Roth
<p>I think that the entire area of data streaming and sub-linear algorithms is an effort in this direction. In data streaming, the focus is on solving the problems in o(n) and ideally O(polylog(n)) space whereas in sub-linear algorithms you try to get algorithms with o(n) running time. In both cases, one often needs to compromise with having randomized approximation algorithm.</p>

<p>You can start with the material on <a href="http://stellar.mit.edu/S/course/6/fa10/6.896/materials.html">this page</a> and <a href="http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html">this</a>.</p>

CC BY-SA 3.0
2012-03-30T03:09:19.030Z
2012-03-30T03:09:19.030Z
Shitikanth
<p>The idea of using approximation algorithms for problems in P is very old and ubiquitous. Several problems in numerical linear algebra including the problem of solving linear systems are solved via iterative methods that converge to the answer quickly. However, they don't always find the exact answer. The rate of convergence to achieve a relative or additive $\epsilon$-approximation is analyzed as a function of the problem size and $\epsilon$. There are a number of papers on solving special cases of linear programming problems such as multicommodity flows (and more generally packing and covering LPs) approximately. There is no separate theory of approximation for problems in P vs problems that are in NP (we don't know whether P is equal to NP or not). One can talk about a certain technique being applicable for a certain class of problems. For instance there are general techniques known for approximately solving packing and covering linear programs and some variants. </p>

CC BY-SA 3.0
2012-03-30T17:09:23.347Z
2012-03-30T17:09:23.347Z
Chandra Chekuri
<p>Dimitris mentions approximating fourier transforms. there is a wide use of this in image compression eg in the JPEG algorithm.[1] although I havent seen a paper that emphasizes this, it seems in some sense a <em>lossy compression</em>[2] (with derivable limits) can also be taken as a P-time approximation algorithm. the approximation aspects are highly developed and finetuned/specialized in the sense they are optimized so that they cannot be perceived by human vision, i.e. the human perception of encoding artifacts (roughly defined as difference between approximation and the lossless compression) is minimized. </p>

<p>this is related to theories about how the human eye perceives or itself actually "approximates" color encoding via some algorithmic-like process. in other words the theoretical approximation scheme/algorithm is actually intentionally designed to match the physical/biological approximation scheme/algorithm (encoded by biological info processing ie neurons in the human visual system).</p>

<p>so, the compression is tightly coupled with the approximation. in JPEG the fourier transform is approximated by the DCT, discrete cosine transform[3]. similar principles are employed over multiple frames for the MPEG video compression standard.[4] </p>

<p>[1] <a href="http://en.wikipedia.org/wiki/JPEG" rel="nofollow">jpeg compression, wikipedia</a></p>

<p>[2] <a href="http://en.wikipedia.org/wiki/Lossy_compression" rel="nofollow">lossy compression, wikipedia</a></p>

<p>[3] <a href="http://en.wikipedia.org/wiki/Discrete_cosine_transform" rel="nofollow">DCT, discrete cosine transform, wikipedia</a></p>

<p>[4] <a href="http://en.wikipedia.org/wiki/Mpeg" rel="nofollow">MPEG, wikipedia</a></p>

CC BY-SA 3.0
2012-04-01T15:57:56.380Z
2012-04-01T15:57:56.380Z
vzn
<p>May be this is not exactly answers your question, because currently I can just remember some heuristics, but I'm sure there are some approximations, because I saw them before.</p>

<p>In some fields like FPT(Fixed parameter tractable) you have a problem, normally in graphs, which can be solved in $O(f(k)*|G|^\alpha)$, like solving TSP in bounded tree width graphs, Or finding tree decomposition of graphs with small tree width. But actually they aren't good enough and $f(k)$ is too large to be used in real world. So using approximations or heuristics are fine here, for example you can take a look at <a href="http://web.eecs.utk.edu/~langston/projects/papers/tmerge.pdf" rel="nofollow">heuristic for TSP in bounded tree-width graphs</a>, or some algorithms for <a href="http://www-ist.massey.ac.nz/mccartin/Mypubs/MAF.04.07.pdf" rel="nofollow">Maximum Agreement Forest</a> problem and its later approximations/heuristics (simple google shows results in 2010, 2011), or algorithms for finding tree decomposition of graphs.</p>

CC BY-SA 3.0
2012-03-31T21:57:54.003Z
2012-03-31T21:57:54.003Z
Saeed
<p><a href="http://www.sciencedirect.com/science/article/pii/S0020019002003939" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0020019002003939</a></p>

<p>is a link to the article "A simple approximation algorithm for the weighted matching problem" by Doratha Drake and Stefan Hougardy covering the weighted matching problem.</p>

CC BY-SA 3.0
2013-05-13T14:56:04.473Z
2013-05-13T14:56:04.473Z
user13407
<p>As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($1/\epsilon$)) sized kernel from the data, and running an expensive algorithm on that kernel, with a guarantee that an exact solution on the kernel is an approximate solution on the entire input. </p>

<p>There are a number of tricks, reductions and principles, and <a href="http://rads.stackoverflow.com/amzn/click/0821849115">Sariel Har-Peled's new book</a> is full of these. I don't think there's a rich complexity theory as such. </p>

CC BY-SA 3.0
2012-04-01T10:39:29.967Z
I think this is the closest to a "theory" that one could get. I will take a thorough look at the book. Thanks!
aelguindy
CC BY-SA 3.0
2012-03-28T17:35:17.657Z
2012-03-28T17:35:17.657Z
Suresh Venkat
<p>One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.</p>

<p>Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.</p>

<p>Three questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?</p>

CC BY-SA 3.0
2012-03-27T22:41:43.190Z
Computational geometry (e.g., $\epsilon$-nets) and numerical linear algebra (e.g., various iterative methods) provide plenty of examples of approximation algorithms for problems that are trivially in P, but exact polynomial-time algorithms may be prohibitively expensive for huge real-world data sets.
Jukka Suomela
CC BY-SA 3.0
2012-03-27T23:47:20.423Z
See http://cstheory.stackexchange.com/questions/9998/approximation-schemes-for-p-complete-problems.
Tsuyoshi Ito
<ds.algorithms><approximation-algorithms>
Approximation algorithms for problems in P
aelguindy
# Approximation algorithms for problems in P

(Asked by: username_0 on 2012-03-27)

One usually thinks about approximating solutions (with guarantees) to NP-hard problems. Is there any research going on in approximating problems already known to be in P? This might be a good idea for several reasons. Off the top of my head, an approximation algorithm may run with a much lower complexity (or even a much smaller constant), might use less space or might be much better parallelizable.

Also, schemes that provide time/accuracy tradeoffs (FPTAS's and PTAS's) might be very attractive for problems in P with lower bounds that are unacceptable on large inputs.

Three questions: is there anything that I'm missing that makes this obviously a bad idea? Is there research going on in developing a theory of these algorithms? If not, at least, is anyone familiar with individual examples of such algorithms?

**Tags:** ds.algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Computational geometry (e.g., $\epsilon$-nets) and numerical linear algebra (e.g., various iterative methods) provide plenty of examples of approximation algorithms for problems that are trivially in P, but exact polynomial-time algorithms may be prohibitively expensive for huge real-world data sets.  
> **username_2**: See http://cstheory.stackexchange.com/questions/9998/approximation-schemes-for-p-complete-problems.  

---

## 11 answers

### Answer by username_13 on 2012-03-28. Score: 21 | Accepted answer

As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($1/\epsilon$)) sized kernel from the data, and running an expensive algorithm on that kernel, with a guarantee that an exact solution on the kernel is an approximate solution on the entire input.

There are a number of tricks, reductions and principles, and [Sariel Har-Peled's new book](http://rads.stackoverflow.com/amzn/click/0821849115) is full of these. I don't think there's a rich complexity theory as such.

> **Comments:**
> **username_0**: I think this is the closest to a "theory" that one could get. I will take a thorough look at the book. Thanks!  

---

### Answer by username_5 on 2012-03-28. Score: 15

Non-exhaustive list of recent papers that find approximate solutions for problems in $P$

1) There is a great amount of work on approximate solutions for linear equations (symmetric diagonally dominant) in nearly linear time $\mathcal{O}(n\cdot\text{polylog}(n))$

(list of papers) <http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html>

(In general most iterative solvers for linear equations share the principle of $\epsilon$-approximating the true solution. The same goes for iterative methods that solve more general problems (e.g., some convex/linear programs)).

2) Approximate solutions to min/max $s-t$ cuts/flows
<http://people.csail.mit.edu/madry/docs/maxflow.pdf>

3) Finding a sparse approximation of the Fourier transform of a signal in sublinear time <http://arxiv.org/pdf/1201.2501v1.pdf>

4) Finding the approximate principal component of a matrix <http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf>


---

### Answer by username_3 on 2012-03-28. Score: 11

I am not aware of a general theory being developed on approximation algorithms for problems in P. I know of a particular problem, though, that is called approximate distance oracles:

> Given a weighted undirected graph $G = (V, E)$ with $n = |V|$ nodes and $m = |E|$ edges, a point-to-point query asks for the distance between two nodes $s, t \in V$.

There is a three-way trade-off between space, query time and approximation in the distance oracle problem. One can trivially answer each query exactly (approximation = $1$) in $O(1)$ time by storing the all-pair distance matrix; or in $O(m + n\log n)$ time by running a shortest path algorithm. For massive graphs, these two solutions may require prohibitively large space (to store the matrix) or query time (to run a shortest path algorithm). Hence, we allow approximation.

For general graphs, the state-of-the-art is the [distance oracle of Thorup and Zwick](http://www.cs.tau.ac.il/~zwick/papers/oracle-JACM-revision.ps), which for any given approximation $k$, requires optimal space. It also gives you a nice space-approximation trade-off.

For sparse graphs, a more general space-approximation-time trade-off can be [shown](http://www.cs.illinois.edu/homes/agarwa16/pubs/ismp2012.pdf).


---

### Answer by username_4 on 2012-03-28. Score: 11

We often seek approximate solutions to simple problems like finding shortest path in a graph, finding number of unique elements in a set. The constraint here is that the input is large and we want to solve the problem approximately using a single pass over the data. There are several "streaming" algorithms designed to achieve approximate solutions in linear/near-linear time.

One problem I worked on, is [approximating betweenness centrality](http://dl.acm.org/citation.cfm?id=1777889). This can be solved in $O(nm)$ time on graphs with $n$ vertices and $m$ edges. A linear time algorithm giving a constant factor approximation to betweenness centrality is of very practical importance.


---

### Answer by username_6 on 2012-03-28. Score: 10

Fast approximation algorithms for maximum matching are known. Atleast one that that comes to my mind immediately is <http://arxiv.org/pdf/1112.0790v1.pdf>.


---

### Answer by username_7 on 2012-03-29. Score: 9

Another reason that we will sometimes look for approximation algorithms for problems in $P$ is because there is some other (non-computational) constraint on our algorithm that precludes an exact solution. One example of such a constraint is [differential privacy](http://en.wikipedia.org/wiki/Differential_privacy): differentially private algorithms will necessarily return only approximate solutions. So in recent years, there has been effort to design approximation algorithms for problems that are otherwise easy to solve exactly: e.g. min-cut, low-rank matrix approximation, computing simple summations, etc. Some of these also happen to run more quickly than the exact solution would, but others have running time that is *much* slower than a non-private exact solution.

> **Comments:**
> **username_0**: That's another great motivation for approximation. Thanks for pointing that out!  

---

### Answer by username_8 on 2012-03-30. Score: 8

I think that the entire area of data streaming and sub-linear algorithms is an effort in this direction. In data streaming, the focus is on solving the problems in o(n) and ideally O(polylog(n)) space whereas in sub-linear algorithms you try to get algorithms with o(n) running time. In both cases, one often needs to compromise with having randomized approximation algorithm.

You can start with the material on [this page](http://stellar.mit.edu/S/course/6/fa10/6.896/materials.html) and [this](http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html).


---

### Answer by username_9 on 2012-03-30. Score: 8

The idea of using approximation algorithms for problems in P is very old and ubiquitous. Several problems in numerical linear algebra including the problem of solving linear systems are solved via iterative methods that converge to the answer quickly. However, they don't always find the exact answer. The rate of convergence to achieve a relative or additive $\epsilon$-approximation is analyzed as a function of the problem size and $\epsilon$. There are a number of papers on solving special cases of linear programming problems such as multicommodity flows (and more generally packing and covering LPs) approximately. There is no separate theory of approximation for problems in P vs problems that are in NP (we don't know whether P is equal to NP or not). One can talk about a certain technique being applicable for a certain class of problems. For instance there are general techniques known for approximately solving packing and covering linear programs and some variants.


---

### Answer by username_10 on 2012-04-01. Score: 4

username_5 mentions approximating fourier transforms. there is a wide use of this in image compression eg in the JPEG algorithm.[1] although I havent seen a paper that emphasizes this, it seems in some sense a *lossy compression*[2] (with derivable limits) can also be taken as a P-time approximation algorithm. the approximation aspects are highly developed and finetuned/specialized in the sense they are optimized so that they cannot be perceived by human vision, i.e. the human perception of encoding artifacts (roughly defined as difference between approximation and the lossless compression) is minimized.

this is related to theories about how the human eye perceives or itself actually "approximates" color encoding via some algorithmic-like process. in other words the theoretical approximation scheme/algorithm is actually intentionally designed to match the physical/biological approximation scheme/algorithm (encoded by biological info processing ie neurons in the human visual system).

so, the compression is tightly coupled with the approximation. in JPEG the fourier transform is approximated by the DCT, discrete cosine transform[3]. similar principles are employed over multiple frames for the MPEG video compression standard.[4]

[1] [jpeg compression, wikipedia](http://en.wikipedia.org/wiki/JPEG)

[2] [lossy compression, wikipedia](http://en.wikipedia.org/wiki/Lossy_compression)

[3] [DCT, discrete cosine transform, wikipedia](http://en.wikipedia.org/wiki/Discrete_cosine_transform)

[4] [MPEG, wikipedia](http://en.wikipedia.org/wiki/Mpeg)


---

### Answer by username_11 on 2012-03-31. Score: 1

May be this is not exactly answers your question, because currently I can just remember some heuristics, but I'm sure there are some approximations, because I saw them before.

In some fields like FPT(Fixed parameter tractable) you have a problem, normally in graphs, which can be solved in $O(f(k)\*|G|^\alpha)$, like solving TSP in bounded tree width graphs, Or finding tree decomposition of graphs with small tree width. But actually they aren't good enough and $f(k)$ is too large to be used in real world. So using approximations or heuristics are fine here, for example you can take a look at [heuristic for TSP in bounded tree-width graphs](http://web.eecs.utk.edu/~langston/projects/papers/tmerge.pdf), or some algorithms for [Maximum Agreement Forest](http://www-ist.massey.ac.nz/mccartin/Mypubs/MAF.04.07.pdf) problem and its later approximations/heuristics (simple google shows results in 2010, 2011), or algorithms for finding tree decomposition of graphs.


---

### Answer by username_12 on 2013-05-13. Score: 1

<http://www.sciencedirect.com/science/article/pii/S0020019002003939>

is a link to the article "A simple approximation algorithm for the weighted matching problem" by Doratha Drake and Stefan Hougardy covering the weighted matching problem.


---

