Bin-packing and matchings in threshold graphs (Q1900150): Difference between revisions

For \(z\in (0, 1]^n\), let \(L_n(z)\) be the number of bins in an optimal solution to the bin-packing problem \(z\). Using some version of the first fit decreasing heuristic FFD, the author obtains the following explicit formulae: \[ \begin{aligned} \text{Exp}(L_{2m}(Z)) & = m+ (2m- 1) (\begin{smallmatrix} 2(m- 2)\\ m- 1\end{smallmatrix}) 2^{- 2m+ 1},\\ \text{Exp} (L_{2m+ 1}(Z)) & = m-\textstyle{{1\over 2}}+ (2m+ 1)(\begin{smallmatrix} 2m\\ m\end{smallmatrix}) 2^{- 2m- 1}.\end{aligned} \] They imply \[ \text{Exp}(L_n(Z))\to \lfloor\textstyle{{n\over 2}}\rfloor+ \sqrt{\overline 2\pi^{- 1}} \overline n, \] where \(\to\) means stochastic convergence.