# Questions tagged [approximation-algorithms]

An approximation algorithm is an algorithm that finds an approximate solution to a (typically NP-hard) problem. The quality of the algorithm is measured by how close to the actual optimum it performs. For example, it is a constant factor approximation algorithm if it always outputs a solution that is within a constant factor of the optimum. Hardness of approximation is one way to separate NP-hard problems.

144 questions
Filter by
Sorted by
Tagged with
703 views

This is another question about visualization of Ford circles, the previous one being Confusion with practically implementing rational approximations. Here is an output of zooming into Ford circles at $... 10 votes 3 answers 669 views ### Approximate volume computation and lattice point enumeration - hardness Both volume computation and lattice point enumeration of convex polyhedron are$\#P$hard. However there is a randomized polytime algorithm for constant factor approximation for volume computation. ... 10 votes 1 answer 279 views ### Confusion with practically implementing rational approximations Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ... 9 votes 1 answer 858 views ### State of the art in the expected length of the Longest Increasing Subsequence of a random permutation I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length$n$. It is easy to see that we are ... 8 votes 6 answers 7k views ### How to approximate a solution to a matrix equation? [closed] Suppose a matrix equation Ax = b has no solution (b is not in the column space of A) How ... 8 votes 1 answer 474 views ### Polynomial approximations of curves This is the 3D version of this question. The responses to that question contained a lot of complaints about fuzzy definition of the problem, so I made this new question very narrow and explicit. For ... 8 votes 1 answer 610 views ### How to evaluate binomial coefficients efficiently and as correctly as possible? This question is more precisely about evaluation with a computer, of a binomial coefficient of the form$ \binom{x}{m}$where$x$is a real number and$m$a rational integer. The reason why I ask is ... 7 votes 1 answer 357 views ### Counting spanning trees of a planar graph I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity$O(N^{2.373}$). I was wondering if anyone was aware of a ... 7 votes 1 answer 150 views ### Metric TSP with integer edge cost Given a metric TSP with integer edge cost upper-bounded by a constant$C_{\max}$, can we find an poly-time algorithm solving this TSP instance? 7 votes 1 answer 536 views ### Norms of B-spline coefficients In Shumaker's book (Spline Functions: Basic Theory), we know that the$l^\infty$-norm of B-spline coefficients is bounded above and below by the$L^\infty$-norm of the spline itself. Are there similar ... 7 votes 0 answers 244 views ### Quantum Optimization as approximating$\mathbb{CP}^{2^n -1}$with the orbits of a subgroup of SU($2^n$) For example given a great circle within the sphere, we can think about computing the average distance of a point on the sphere from the great circle. Slightly more generally, given a subgroup$H \... 1k views

### Approximating $e$ with 2s and 3s

How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to $e$ as possible? For example: ...
466 views

### Approximating derivatives between gridpoints

Suppose we have a grid (possibly irregular) of $N$ function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more). What would be a good way to ...
I can use software to calculate the Betti numbers $\beta_0,\beta_1,\beta_2,\dots$ of a finite simplicial complex. This is prohibitive for large complexes, built on say > 100,000 nodes. Is there some ...