# Recommend: Approximation Algorithm Book?

This topic is 2175 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I was wondering if anyone has had any familiarity with approximation algorithms, and if they know of any good introductory texts to the topic.

##### Share on other sites

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.

##### Share on other sites

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.

##### Share on other sites

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).

##### Share on other sites

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.

Edited by DevLiquidKnight

##### Share on other sites

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

##### Share on other sites

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 .

##### Share on other sites

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

• 12
• 18
• 29
• 11
• 24