**0**

votes

**2**answers

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

**8**

votes

**1**answer

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

**0**

votes

**0**answers

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

**1**

vote

**2**answers

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

**6**

votes

**2**answers

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

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

**16**

votes

**2**answers

439 views

### “Fractally self-similar” numbers

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

**1**answer

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

**1**

vote

**0**answers

23 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**3**

votes

**0**answers

108 views

### Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor.
Group TSP is defined as follows: Take a ...

**7**

votes

**1**answer

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

**3**

votes

**0**answers

153 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**3**

votes

**0**answers

34 views

### Solving a Certain Constrained Isoperimetric Approximation-Problem

This question is related to my question Differential Geometric Aspects of Rubber Bands, where I asked for a mathematical model of contracting rubber bands.
In contrast to my former question, the ...

**5**

votes

**0**answers

81 views

### Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.)
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...

**1**

vote

**0**answers

63 views

### FPTAS for approximating the permanent of a matrix

My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...

**3**

votes

**0**answers

147 views

### Estimating the growth rate of nondeterministic finite automata

Given a nondeterministic finite automaton $\mathcal{A}$ (or a regular expression, or a regular grammar), can we efficiently compute the number $|L_k(\mathcal{A})|$ of accepted words of length $k$?
No,...

**7**

votes

**0**answers

139 views

### Nearest Point to a real algebraic set

Suppose I have a compact bounded real algebraic (eventually: or analytic or semialgebraic or semianalytic set) $V$ in $\mathbb R^3$ and a point $x\in\mathbb R^3$ not in $V$. How much do we know about ...

**2**

votes

**3**answers

239 views

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

Let $f$ be a monic univariate polynomial with real coefficients:
$$f_A(x) = x^n + a_{n-1}x^{n-1} + ... + a_{0}$$
The values of $A=(a_{n-1},...,a_0)$ are unknown, but are estimated as $B=(b_{n-1},...,...

**1**

vote

**1**answer

60 views

### Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \...

**3**

votes

**3**answers

923 views

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

How to construct the optimal piece-wise linear continuous function fitting given curve and given number of knots (optimal knots positions also must be determined by this method)?

**1**

vote

**1**answer

99 views

### Computing row-sum scaled unsigned Stirling nos. of the 1st kind

As the title suggests, I would like to compute probability vectors with elements proportional to (unsigned) Stirling numbers of the first kind by row. For easy reference, here is the Wiki page.
For ...

**6**

votes

**2**answers

247 views

### Approximating the action of the U(N) exponential map

Let's say that I have a curve in $\mathbb{C}^N$ given by the action of the unitary group:
$$x(t) = e^{Ht}x_0,~ H \in \mathfrak{u}(N),~ ||x_0||=1$$
Here, $H$ is an NxN skew-Hermitian matrix (for very ...

**0**

votes

**0**answers

35 views

### Inapproximability of logarithmic factor of independent set

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...

**1**

vote

**1**answer

61 views

### How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ d(...

**1**

vote

**1**answer

60 views

### Heuristic for choosing n-vectors from n-sets

my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...

**3**

votes

**2**answers

290 views

### Approximation of curves

When constructing minimax (sup-norm) polynomial approximations of real-valued functions, well-known results say (roughly speaking) that optimal solutions are characterized by the fact that they have ...

**1**

vote

**2**answers

186 views

### Bivariate Function Approximation

I am working on a nonlinear control design and having difficulty in finding approximation of bivariate functions. Are there papers or methods discussing the following question:
For any bivariate ...

**2**

votes

**1**answer

86 views

### Convergence of Symmetric Iterative Proportional Fitting

Let $A$ denote a symmetric matrix of non-negative entries, whose rows (and columns) sum up to the all-positive vector $d := A\mathbf{1}$ with $\mathbf{1}$ the all-one-vector. Denote $D := diag(d)$ by ...

**0**

votes

**1**answer

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

**4**

votes

**1**answer

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

**1**

vote

**1**answer

260 views

### Approximation of a given function by rational functions

Given a function $1/\sqrt{x^2 -k^2}$ where k is a constant with a small imaginary part, how do you go about constructing a rational approximation? I am interested in the L_p (p=2 or $\infty$) norm of ...

**3**

votes

**0**answers

311 views

### Tiling a rectangle with weighted cells (min-max problem)

I have been struggling with a research problem. The problem can be formalized as follows:
Given a $n\times m$ matrix $A$ containing cells with non-negative integer values, partition it in $J$ ...

**3**

votes

**2**answers

2k views

### Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix?
The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...

**4**

votes

**2**answers

314 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**3**

votes

**1**answer

426 views

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...

**1**

vote

**1**answer

152 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**4**

votes

**0**answers

192 views

### envelope function for a linear combination of gaussian distributions

Given a distribution $F$ defined as a linear combination of Gaussian distributions:
$F = \sum_{i=1}^n C_i*N(\mu_i,\sigma_i)$ with $\sum_{i=1}^n C_i = 1$
I want to find a Gaussian function $Q = a*e^{\...

**3**

votes

**0**answers

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

**3**

votes

**3**answers

787 views

### iteratively (approximately) solving a sum of exponentials

I would iteratively have to solve the following equation at iteration $n$:
$C = \sum_{1 \leq i \leq n}{e^{\frac{x_i}{T}}x_i}$ for $T$.
Each iteration $i$ an unknown $x_i$ will be observed and $C$ is ...

**0**

votes

**1**answer

342 views

### Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.
Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise
Let $b_{t+1}...

**3**

votes

**1**answer

164 views

### Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...

**0**

votes

**0**answers

67 views

### Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity
\begin{equation}
\sum_{k=1}...

**1**

vote

**0**answers

181 views

### Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...

**2**

votes

**1**answer

1k views

### Removing cycles from an undirected connected bipartite graph in a special manner

Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We ...

**1**

vote

**2**answers

134 views

### Near-linear Function aproximation

Hi,
I have a growing, near-linear function, that has some "noise" in its linearity. Is there any solution, how to approximate this function ? I tried Neural Network, but ist not best...
Function ...

**0**

votes

**2**answers

383 views

### Enlcosing a set of ellipses within one ellipse

Hello,
Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?

**4**

votes

**4**answers

1k views

### When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...

**2**

votes

**0**answers

136 views

### A.G. Vitushkin's “Easily representable families of functions” - can it be generalized?

Background
In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...

**0**

votes

**0**answers

161 views

### Pure greedy algorithm

I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that
$\|f-G_m(f,D)\|>Cm^{-1/2}\lvert\{f}\...