The approximation-algorithms tag has no wiki summary.
0
votes
0answers
8 views
How to handle the integral and non-integral values in Graph Theory optimization problems.
In graph theory optimization problems, when the values are integer, it is "easy" to handle (at least we can find some combinatorial tools) , but when the values are not integral, we even dont know how ...
1
vote
0answers
39 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
0answers
30 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
1answer
82 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
0answers
28 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
1answer
177 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 ...
-1
votes
1answer
85 views
Recursion equation convergence to sqrt [closed]
I'm new here. I have a recursion equation
$$
a[n] = \frac{n \cdot a[n-1]}{n+a[n-1]} + k
$$
$$
a[1] = 1
$$
$$
k \in \mathbb{R}, k > 0
$$
and from computing and ploting graphs I found that it can ...
3
votes
0answers
194 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
2answers
548 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
2answers
147 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
1answer
140 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
121 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
90 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
51 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
29 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 ...
3
votes
3answers
426 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
179 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 ...
3
votes
1answer
125 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
55 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
100 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
1answer
264 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
114 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
210 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
705 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
101 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
0answers
149 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
...
3
votes
2answers
295 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.
...
3
votes
1answer
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?
...
1
vote
0answers
63 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
0answers
231 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}( ...
8
votes
0answers
367 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 ...
1
vote
0answers
211 views
Multiobjective semidefinite programming
Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...
4
votes
1answer
466 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?
...
4
votes
2answers
470 views
Getting started: combinatorial optimization for computer scientists
I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems.
I have good knowleges of graphs, *-flow algorithms and so ...
0
votes
0answers
99 views
sparsest cut always has solution
Hi!
How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.
Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
1
vote
1answer
194 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 ...
1
vote
0answers
441 views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
2
votes
2answers
490 views
biggest cube problem (given set of bricks)
Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces.
Problem: find the way of putting together those pieces to make a solid that contains biggest ...
5
votes
0answers
223 views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
4
votes
1answer
772 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$ ...
0
votes
0answers
268 views
Approximate a piecewise linear path by a path with bounded curvature
I have a piecewise linear path in two dimensions (with finitely many pieces). I would like to approximate it by a curve whose radius of curvature is bounded away from 0 (i.e. I specify the bound a ...
1
vote
2answers
1k views
Greedy approach to 0-1 Knapsack problem in specific instances
The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
4
votes
2answers
324 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
3
votes
0answers
189 views
Algorithm for testing satisfiable fraction of linear equations mod 2
Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation ...
1
vote
2answers
301 views
Approximation of conformal mapping as a sum of elementary conformal mappings
Hi,
I would like to approximate any 2d conformal mapping, as a sum of elementary conformal mappings. So I would have some basis, a conformal mapping with some parameters, and by adding several ones ...
5
votes
2answers
506 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 ...
6
votes
3answers
857 views
Approximating e with 2s and 3s
How can I generate a series of 2s and 3s such that the average of the generated values (so far) is as close to e as possible?
For example:
...
4
votes
3answers
365 views
Approximating derivatives between gridpoints
Hi,
Suppose we have a grid (possibly irregular) of N function/value pairs, $(x_i, f_i)$, $i=1...N$. The function is differentiable everywhere at least twice (perhaps more).
What would be a good way ...
0
votes
1answer
2k views
HOW TO Generate Equation of a Curve Given (x,y) pairs - algorithm? [closed]
Hi,
How can I generate the equation of a curve that matches all arbitrarily given (x,y) pairs? I would like a polynomial of nth degree, where n does not matter, as long as the curve passes thru all ...
1
vote
2answers
632 views
Approximate Algorithms for Poisson's Equation (PDE)
Are there some approximate or randomised algorithms to numerically solve Poisson's Equation in Partial Differential Equations.(http://en.wikipedia.org/wiki/Poisson%27s_equation). The best algorithms I ...
