The approximation-algorithms tag has no wiki summary.

**0**

votes

**0**answers

13 views

### How to solve a special linear system with noise?

Sorry the title may be confusing. I'm not so sure how to categorize this problem.
Anyway, We have a real-valued vector $\overrightarrow a=(a_0,a_1,...,a_{2^n-1})$. Each $a_i$ comes from the inner ...

**3**

votes

**0**answers

91 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$?
...

**0**

votes

**1**answer

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

**2**

votes

**0**answers

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

**5**

votes

**0**answers

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

59 views

### Mixture with varying concentrations

Let $(\Omega ,\mathcal F, \mathbb P)$ be a probability space and suppose $$\mathbb P(X \in A) = H(A) = \prod _{i=1}^m H_i(A),\quad \forall A\in \mathcal F$$ be a distribution of a random vector $X = ...

**4**

votes

**1**answer

71 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

**2**answers

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

**0**

votes

**0**answers

54 views

### Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not.
Which software would you suggest for rigid transformations?
Thank you

**3**

votes

**3**answers

311 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)?

**7**

votes

**0**answers

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

**0**

votes

**1**answer

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

**2**

votes

**3**answers

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

**1**

vote

**1**answer

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

**1**

vote

**1**answer

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

**6**

votes

**2**answers

236 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

29 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

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

**3**

votes

**2**answers

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

**3**

votes

**3**answers

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

**4**

votes

**1**answer

622 views

### Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...

**2**

votes

**0**answers

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

**5**

votes

**2**answers

522 views

### Runge-Kutta method with c<1

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...

**4**

votes

**1**answer

796 views

### Searching for an inhomogeneous diophantine approximation algorithm

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, what is an algorithm that will provide coprime integers $a$ ...

**3**

votes

**0**answers

259 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

345 views

### How to check numerical precision of my computation of Stieltjes-constants?

In a thread in MSE I proposed an older routine of mine for the efficient computation of coefficients; I use a very similar routine for the quick&dirty computation of the Stieltjes-constants.
...

**1**

vote

**1**answer

235 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

**2**answers

1k 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

238 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

319 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

140 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

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

**3**

votes

**0**answers

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

**0**

votes

**1**answer

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

**4**

votes

**1**answer

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

**3**

votes

**1**answer

153 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

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

**1**

vote

**0**answers

150 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

580 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

126 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

290 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

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

**4**

votes

**2**answers

441 views

### Set Cover:Greedy vs LP

Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks

**1**

vote

**1**answer

227 views

### Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets ...

**0**

votes

**0**answers

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

**1**

vote

**0**answers

69 views

### An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label).
We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...

**3**

votes

**0**answers

237 views

### Place n telescopes on a sphere in R^d to see the whole sky

Where would one put $n$ telescopes on the surface of the earth
to see the whole sky as well as possible ?
Use the cosine metric to define how well we can see in direction $x$:
$ \qquad \text{cansee}( ...