1
vote
2answers
33 views

Approximating 'big' ratio with 'small' ratio

Given a ratio $ \frac{m}{n}, p \in N, q \in N $ where either $m$ or $n$ (or both) is a very big number, how can we find a ratio $ \frac{p}{q}, p \in N, q \in N $ which estimates $ \frac{m}{n} $ up to ...
0
votes
1answer
69 views

ln-exp approximation

I am looking for an approximation to the following expression: $\ln (1+e^{-x})$ If $x$ is small then it is not a problem. However, is there a (polynomial, rational) approximation for relatively ...
0
votes
0answers
29 views

exponential approximation

I am reading about AdaBoost algorithm, I cannot understand (7). How can it be like this? If you want full document, you can get it at http://cseweb.ucsd.edu/classes/fa01/cse291/AdaBoost.pdf Thank ...
2
votes
0answers
25 views

Non Approximation result

Say we have a constant approximation algorithm for the following objective: $$\min_x f(x) \;\;\;\;\;\; (1)$$ Now, we want to solve the following objective: $$ \max_x (N - f(x)) \;\;\;\;\;\; (2) ...
5
votes
3answers
47 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
2
votes
0answers
41 views

Is there a known algorithm for approximating all the real and imaginary zeros of any well behaved equation of a single variable?

Does there currently exist a general algorithm (or set of algorithms used together) that will approximate all the zeros of any well behaved non-differential equation of a single variable which has a ...
3
votes
2answers
161 views

Simple problem whose approximation ratio is still open.

I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has ...
0
votes
1answer
35 views

Algorithm to approximate the closest nonlinear formula(funciton) for an arbitrary set of points?

I have a table which concists of XY points (so I have a set of points hehe), where X represents the Velocity and Y the Real World Speed. Those points are not linear. With two points it's easy to ...
0
votes
3answers
90 views

Finding an approximate diagonal in a grid

Imagine a 2 dimensional grid, with a variable size of $ x*y $. For this example of figure 1, let $ x=14; y=5 $. Now one may position "pixels" in this gird. They can only be placed on the grid's points ...
3
votes
1answer
98 views

Iterative model fitting

I have a sequence of points $\{(x_k,y_k,z_k)\}$ and I need to fit some $2D$ model $P(x,y)$ that approximates $z$ in some sense. The $z_k$$'s$ are noisy samples of some $2D$ function $z_k = f(x,y) + ...
3
votes
4answers
161 views

Improving Newton's iteration where the derivative is near zero?

I'm implementing a root-solver for finding x coordinates of a function f(x), after I have an y-coordinate. The function is periodic, roughly sinusoidal with constant amplitude but non-linearly ...
0
votes
0answers
39 views

Steiner Tree Approximation

My question is about a subtlety regarding the $2$-approximation for the Metric Steiner Tree problem. The classical Metric Steiner tree problem: Given a metric space on $n$ points and a subset $S$ ...
0
votes
1answer
94 views

Algorithms for finding closed form approximations for integrals (with no closed form solutions)

It is well known that many integrals have no closed form solutions, normally what you would do is solve them numerically. My question is if there are algorithms that give you good closed form ...
1
vote
4answers
131 views

$\log_2$ approximation in $[1,2)$

this is realistically for a programming project, but is more math centric then CS centric. I am attempting to write a function that approximates a power function, but in order to complete I need to ...
0
votes
2answers
209 views

How does this square root approximation work?

I've come across an odd way of estimating the square root of a number, going like this: Given a number n, Subtract the odd numbers from n in a rising order (1, 3, 5...), until $n \leq 0$ Count how ...
2
votes
0answers
68 views

Algorithm to predict next 3D points

For example, having this data: year x/y/z 2007 10/20/70 2008 20/10/70 2009 30/10/60 2010 40/10/50 2011 40/15/45 We want to predict what will be the x/y/z in ...
1
vote
1answer
45 views

Approximation of closest k-coloured points?

I'm a working software engineer faced with the following problem: I have a set of points on a 2d plane. Each point can have one of $k$ different colours. I wish to select one point of each colour that ...
0
votes
2answers
1k views

Easy approximation of the incomplete beta function $\text{B}_x(a,b)$

I need to calculate $\text{B}_x(a,b)$ on the cheap, without too many coefficients and loops. For the complete $\text{B}(a,b)$, I can use $\Gamma(a)\Gamma(b)/\Gamma(a+b)$, and Stirling's approximation ...
3
votes
0answers
183 views

Approximation of a real number as a linear combination of two reals with coprime integral coefficients

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$, give me an algorithm that will provide coprime integers $a$ ...
2
votes
0answers
157 views

calculate the rate of change

I am trying to calculate the change frequency for a set of data. Each bit of data has the date-time it was created. I would like to say for a specific set of data the change frequency is hourly, ...
0
votes
1answer
99 views

Development of a specific hardware architecture for a particular algorithm. Modelling fuctions by Taylor sSeries.

I'm trying to develop a architecture hardware to make a implementation of an algorithm that can be descompose in terms of sums, multiplications, subtractions and exponential functions. I'm trying to ...