Approximation algorithms for problems in P

Question

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?

Answer 1

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 is full of these. I don't think there's a rich complexity theory as such.

Answer 2

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 3

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, 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.

Answer 4

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. 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 5

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 6

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: 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.

Answer 7

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 and this.

Answer 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 9

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 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

[2] lossy compression, wikipedia

[3] DCT, discrete cosine transform, wikipedia

[4] MPEG, wikipedia

Answer 10

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, or some algorithms for Maximum Agreement Forest problem and its later approximations/heuristics (simple google shows results in 2010, 2011), or algorithms for finding tree decomposition of graphs.

Answer 11

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.