Recommend: Approximation Algorithm Book?

Start with regression analysis and least squares

http://en.wikipedia.org/wiki/Regression_analysis

Basically you fit a polynomial through a curve and you choose the coefficients of the polynomial by minimising the error between the curve and the data using least squares technique.

Easiest case is linear regression, have a look at this page: http://en.wikipedia.org/wiki/Linear_regression

Usually you solve these offline and use a maths/statistics package to do so (MATLAB?). You could do it with a spreadsheet though if you wanted. I don't know if wolfram alpha does that kind of thing, haven't tried it.

You don't have to use polynomials, you can look at the curve and try and fit other suitable curves through the data as well (e.g. sin, cos, log, exp, etc.).

The theory is based on linear algebra (so matrix methods, choosing linearly independent functions as your basis functions).

EDIT: If you want a textbook any text on regression analysis (statistics) should suffice. You will need to know a bit about linear algebra as a prerequisite.

If you want a textbook any text on regression analysis (statistics) should suffice. You will need to know a bit about linear algebra as a prerequisite.

Already have an understanding of this.

There's also approximation theory http://en.wikipedia.org/wiki/Approximation_theory

which is linear algebra again (orthogonal polynomials, Fourier series), which may be better than regression if you want the approximation to be exact at various points (e.g. you'd want an approximation to a sine curve to give correct values at 0 and pi/2 radians).

There's also approximation theory http://en.wikipedia.org/wiki/Approximation_theory

which is linear algebra again (orthogonal polynomials, Fourier series), which may be better than regression if you want the approximation to be exact at various points (e.g. you'd want an approximation to a sine curve to give correct values at 0 and pi/2 radians).

I am sure this is useful, but I am having a hard time seeing how this is related to this:

http://en.wikipedia.org/wiki/Approximation_algorithm

The idea of approximating solutions to NP Hard problems. And such seems more like discrete optimization then statistics, or even linear algebra, I am sure it builds off some of those ideas, after all its all math, However I would like to study it specifically. I am pretty well versed in quite a lot of math Calc1-3, Linear Algebra, Stat, DiffEq, NumTheory, Abstract Algebra, so I am not really worried the fundamentals so much.

Oops, I thought you were after approximations to functions ;)

I figured you were thinking as much. I should of been more clear, approximation algorithms isn't a lot to go on I guess. No harm done, I just hope someone has a suggestion .

I figured you were thinking as much. I should of been more clear, approximation algorithms isn't a lot to go on I guess. No harm done, I just hope someone has a suggestion .

Try searching for 'heuristic algorithms'.

-Josh