13 votes
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
9 votes
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 ...
8 votes
Accepted

"Fractally self-similar" numbers

Before you can formulate your question precisely, you need a better notion of distance between two pictures of a set $S \subset \mathbb{C}$ (where in this case, $S$ is the union of Ford circles). If $\...
7 votes

"Fractally self-similar" numbers

Define the parent of a Ford circle to be the smaller of its two larger neighbors; then this parent relation defines the Stern–Brocot tree on the points of tangency of the circles. The path in this ...
7 votes

Metric TSP with integer edge cost

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and ...
  • 29.1k
6 votes
Accepted

Approximate volume computation and lattice point enumeration - hardness

Below the line I address the question after "Update" about the relationship between volume and the number of lattice points. Since OP asks about conditions under which we can count the number of ...
5 votes
Accepted

Determining Roots of a Polynomial with Interval Estimates of Coefficients

Polynomials with a multiple root form a Zariski closed set (vanishing of the discriminant, which is a certain polynomial in the coefficients); hence, this set is nowhere dense, whereas its complement ...
5 votes
Accepted

Norms of B-spline coefficients

This question is closely related to the so-called "condition number" of the B-spline basis. Basically, for a spline $f$ of some degree $p$ with a coefficient vector $c=(c_i)$, you generally have for ...
  • 268
4 votes
Accepted

Fast Bourgain embedding (or similar embeddings)?

There is a way to speed-up Bourgain's embedding in case if the original metric space has low "intrinsic dimension". The resulting algorithm will have a theoretical runtime $O(CN\log^2(N))$, where $C$ ...
4 votes
Accepted

Can you solve this problem using a finite number of queries?

The question is stated informally, using the terms "queries" and "access". Here is how I formally interpret it: Take any $s$ and $t$ in $(0,1)$. Let $G_{s,t}$ be the set of all ...
3 votes
Accepted

2-approximation algorithm for Minimum Maximal Matching (MMM) problem

There is an easy $2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching $M$ can be found greedily. Initialize $M=\...
  • 29.1k
3 votes
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, ...
3 votes

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, ...
3 votes
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
3 votes
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
3 votes
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
2 votes

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 ...
2 votes

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 ...
2 votes
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 ...
2 votes

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 ...
2 votes

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 ...
2 votes

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

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
2 votes
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^*$ ...
2 votes
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
2 votes

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

A variation of longest paths in directed acyclic graph

It’s NP-hard to approximate this within any constant factor, by a reduction from 2-CSP (that it is hard to approximate 2-CSP follows from the PCP theorem and parallel repetition). Suppose I have an ...
  • 8,185
2 votes

The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

(EDITED) Changing one element can never decrease the rank by more than $1$, so changing $k$ elements can never decrease it by more than $k$. For at least some cases we can arrange to decrease it by $...
2 votes
Accepted

complexity of bounded knapsack with spoilage

This was my question to start with, and I think I have figured out how to solve it in pseudopolynomial time. We can order the items by value, from largest to smallest, and guess what is the last (...
2 votes
Accepted

Subdividing a sequence such that sum is somewhat equally distributed

You can solve the problem exactly as a shortest path problem in a layered network. The nodes are $(i,k)$, where $i\in\{n,\dots,1\}$ and $k\in\{1,\dots,M\}$. The (directed) arcs are from $(i,k)$ to $(...
  • 3,915

Only top scored, non community-wiki answers of a minimum length are eligible