# Tagged Questions

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

257 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
69 views

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

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...
124 views

### Relaxed path decomposition of a graph

Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
373 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 ...
53 views

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

It is well known that various real root isolation methods are based on computing, first, the bounds on the values of the positive real roots of a polynomial equation. For the univariate case such ...
849 views

### What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm(). According to ...
53 views

### Asymptotic determinant of $2\times 2$ Toeplitz matrix

The problem that I am dealing with is to compute the determinant of a $2\times 2$ Toeplitz matrix[1] (in general I would like to generalize to a more general case, but let's consider the easiest case ...
518 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 ...
35 views

### Matrix Completion: Clearing Step

I am trying to implement Keshavan, Montanari and Oh (2009) algorithm for Matrix Completion. It consists of three steps: 1) Trimming which nulls some rows and columns to make the high singular values ...
2k views

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

Hi. Imagine that a user draws on the canvas any path. I want to approximate this path with a path $P(x,y)=0$ where $P(x,y)$ - is unknown polynom. May be somebody can suggest an appropriate algorithm? ...
439 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?
The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...