# Offline bin-packaging problem: probability of a non-optimal solution for the first-fit-decreasing algorithm

For the offline bin packaging problem (non-bounded number of bins, where each bin has a fixed size, and a input with known size that can be sorted beforehand), the first-fit-decreasing algorithm (FFD) gives a solution whose number of bins is, at most, $$\frac{11}{9}\times S_{opt} + \frac{6}{9}$$, or, for the sake of simplification, around $$23\%$$ bigger than the optimal number of bins ($$S_{opt}$$).

Has the probability of getting a non-optimal solution using FFD been ever calculated? Or, in other words, what is the probability of getting a solution whose exact size is $$S_{opt}$$? Or do we have no other choice than assuming that the solution size is evenly distributed in the interval $$[S_{opt}, \frac{11}{9}\times S_{opt} + \frac{6}{9}]$$? Or, as another alternative I can think of right now, is the solution size so dependant on the input that making this question has no sense at all?

And, as a related question, is there any research about what is the NP-hard or NP-complete problem that has an approximation algorithm (of polynomial asymptotic order) with the highest probability of providing an optimal solution?