# Tag Info

## Hot answers tagged approximation-algorithms

Accepted

### State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

@user61318 and @JosephORourke, thanks for the advertisement for my book. @chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (...
• 2,166
Accepted

### Counting spanning trees of a planar graph

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated ...
• 82.5k
Accepted

• 29.1k
Accepted

### Confusion with practically implementing rational approximations

It depends on the model of computation you're using. If your memory slots can contain arbitrarily large integers (rather than single bits), and you can perform arithmetic operations in constant time, ...
• 11.8k

### Polynomial approximations of curves

Do you care more about the curve or the surfaces? Replacing the first function in your example by $100(x^2 + y^2 - 16)$ or $x^2-z^2+9$ gives the same curve but a different error function. Also, ...
• 29.6k
Accepted

### Construct the best piece-wise linear continuous function fitting given curve

If the number and position of the knots are fixed, then the problem is a linear least squares problem for determining the coefficients of linear B-Splines (cf e.g http://en.wikipedia.org/wiki/B-spline)...
• 11.3k
Accepted

### Approximate homology of a large simplicial complex

You have to find a way to reduce the size of your simplicial complex. Some algorithms based e.g. on discrete Morse theory can do that fairly rapidly, but they don't have guarantees on the amount of ...
• 2,229
Accepted

### Im looking for an algorithm that can solve or approximate the solution to a problem

You can solve this problem via integer linear programming. Let binary decision variable $x_i$ indicate whether you can open door $i$, and let binary decision variable $y_j$ indicate whether you ...
• 3,915

### How to make an approximation of path with polynom P(x,y)=0?

Your reference to eigenvalues suggests that you are minimizing $\sum_i P(x_i, y_i)^2$ subject to a constraint like $\sum_{a,b} P_{ab}^2=1$, where $P(x,y) = \sum_{a,b} P_{ab} x^a y^b$. Why not instead ...
• 141k

### How to evaluate binomial coefficients efficiently and as correctly as possible?

Since you're using sage, I'd write a quick C or Cython function. Use the Arb library (I think this is already included in the latest release of sage) by computing the function in the naive way using ...
Accepted

### Bounds on the positive roots of a bivariate polynomial

To bound the roots of a bi-variate system of polynomial equations you can use resultants. As a simple example, look at the following set of equations: $$x^2+y^2-4=0 \\ xy-1=0$$ which correspond to ...
• 616

### How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

Since each row $r$ has a finite number of non-zero elements, say $N_r \subset \{1, 2, \dots\}$, you could use the Gillespie algorithm to simulate the continuous time Markov chain. A stationary ...

### Determining Roots of a Polynomial with Interval Estimates of Coefficients

You might find the idea of Companion matrix to be useful. The eigenvalues $\lambda$ of the companion matrix $C$ are equal to the roots of a polynomial and its eigenvectors $v$ are functions of the ...
• 690

### Bivariate Function Approximation

Expanding on my comment ... There's some material on bivariate approximation in Carl deBoor's book entitled "A Practical Guide to Splines". Specifically, chapter XVII has results on approximation ...
• 561

### Approximating a function with sums of gaussians

Approximate a function with a sum of sums of gaussians, preferably orthogonal ones. ... the above seems to be related to Radial basis function approximations. Indeed, you could use an RBF ...
• 261
Accepted

### Complementary slackness for approximately optimal Dual solution

Yes, we do have "approximate complementary slackness" in the following sense. Consider the standard (primal) linear programming problem: max $c^T x$ s.t. $A x \le b$, $x \ge 0$ If $x^*$ and $y^*$ ...
• 51.8k
Accepted

### 3-Approximation Algorithm for 3-Hitting Set

Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. Rephrased, our goal is to find ...
• 29.1k

### Approximating John's ellipsoid from uniform sampling of a centrally symmetric convex polyhedron

No, a fixed number of added vertices can change the John ellipsoid by an arbitrary amount when added to arbitrarily many already known vertices: consider a very thin regular n-gon prism centered about ...
• 5,818