0
votes
1answer
18 views

Approximate non-Lipschitz (but continuous) functions by Lipschitz functions

Is there any algorithm to approximate non-Lipschitz (but continuous) functions by Lipschitz functions ?
2
votes
0answers
11 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$$ I can approximate this to first order as: $$\tilde ...
2
votes
1answer
129 views

Upper and lower bound of an approximate computation

I'm currently working on an exercise in The Art Of Computer Programming, Vol. 1 relating the algorithm for computing $\log_{10} x$ presented in the Mathematical Preliminaries. The algorithm is ...
0
votes
0answers
24 views

2-approximation for TSP-metric

I got stuck with the following question: Consider the following heuristic: Start with a tour containing only one vertex. At each step, find the vertex outside the tour with the lesser distance to ...
1
vote
1answer
118 views

Solve non-linear equations of 3 variables using Newton-Raphson Method iterms of c,s and q.

The three non-linear equations are given by \begin{equation} c[(6.7 * 10^8) + (1.2 * 10^8)s+(1-q)(2.6*10^8)]-0.00114532=0 \end{equation} \begin{equation} s[2.001 *c + 835(1-q)]-2.001*c =0 ...
0
votes
1answer
37 views

Understanding graph layering approximation algorithms

I've been trying to understand the Graph Layering Approximation Algorithms for both Set Cover and Feedback Vertex Set problems. I am using Vijay V. Vazirani's "Approximation Algorithms" book. So let ...
1
vote
2answers
36 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
0answers
33 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
29 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
64 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
45 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
169 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
37 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
102 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
109 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) + ...
4
votes
5answers
201 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$ ...
1
vote
1answer
105 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
134 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 ...
2
votes
2answers
255 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
69 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
46 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
192 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
162 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
100 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 ...