I'm reading up on the one dimensional bin packing problem and the different solutions that can be used to solve it.
Bin Packing Problem Definition: Given a list of objects and their weights, and a collection of bins of fixed size, find the smallest number of bins so that all of the objects are assigned to a bin.
Solutions I'm studying: Next Fit, First Fit, Best Fit, Worst Fit, First Fit Decreasing, Best Fit Decreasing
I notice that some articles I read call these "approximation algorithms", and others call these "heuristics". I know that there is a difference between approximation algorithms and heuristics:
Heuristic: With some hard problems, it's difficult to get an acceptable solution in a decent run time, so we can get an "okay" solution by applying some educated guesses, or arbitrarily choosing.
Approximation Algorithm: This gives an approximate solution, with some "guarantee" on it's performance (maybe a ratio, or something like that)
So, my question is are these solutions that I'm studying heuristic or approximation algorithms? I'm more inclined to believe that they are heuristic because we're choosing the next item to be placed in a bin by some "guess". We're not guaranteed of some optimal solution. So why do some people call them approximation algorithms?
If these aren't heuristic algorithms, then what are examples of heuristic algorithms to solve the bin packing problem?
An algorithm can be both a heuristic and an approximation algorithm -- the two terms don't conflict. If some "good but not always optimal" strategy (the heuristic) can be proven to be "not too bad" (the approximation guarantee), then it qualifies as both.
All of the algorithms you listed are heuristic because they prescribe a "usually good" strategy, which is the heuristic. For any of the algorithms where there is an approximation guarantee (the "error" must be bounded somehow), then you can also say it's an approximation algorithm.