The approximation-algorithms tag has no wiki summary.
3
votes
2answers
159 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
116 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
55 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
99 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
47 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
45 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
26 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
244 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
143 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
109 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
72 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
157 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
99 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
182 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
501 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
89 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
136 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
1answer
229 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
57 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
230 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
298 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
198 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
0answers
368 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
431 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
96 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
166 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
417 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
475 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
211 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
705 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
245 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. ...
3
votes
2answers
268 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
176 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
285 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 ...
6
votes
3answers
852 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:
...
5
votes
3answers
355 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
614 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 ...
4
votes
1answer
483 views
Hypergraph Chromatic Number vs Degree, Clique-Size
For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
1
vote
2answers
788 views
Analyzing Weighted Set-Cover variant
A standard greedy algorithm for solving the weighted set-cover problem can be proven to be a $\log(n)$ approximation. I have a variant of weighted set cover, and I came up with a greedy algorithm for ...
