The approximation-algorithms tag has no wiki summary.
3
votes
1answer
45 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
1answer
95 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
0answers
37 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 = ...
2
votes
0answers
42 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
0answers
24 views
Calculate the tendency of a set of samples
I develop an application in which i constantly get samples of heart pulse.
I defined an interval of t seconds.
In each t seconds I have n samples.
In every interval, I want to calculate the ...
2
votes
3answers
223 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
1answer
138 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 ...
2
votes
1answer
103 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
0answers
37 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
0answers
66 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 ...
1
vote
1answer
138 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
2answers
95 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 ...
1
vote
2answers
177 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
4answers
469 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
0answers
88 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 ...
