Jump to content
  • Advertisement
Sign in to follow this  
DevLiquidKnight

Recommend: Approximation Algorithm Book?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement

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.

Edited by Paradigm Shifter

Share this post


Link to post
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. smile.png

Share this post


Link to post
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. smile.png 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 this post


Link to post
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 smile.png.

Share this post


Link to post
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 smile.png.

 

Try searching for 'heuristic algorithms'.

 

-Josh

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!