Next-fit packs a list and its reverse into the same number of bins (Q1109684)

Suppose the next-fit algorithm packs \(\{x_ 1,x_ 2,...,x_ n\}\) into k identical bins. Under modest assumptions about what fits into a bin, we prove that next-fit also packs \(\{x_ n,...,x_ 2,x_ 1\}\) into k bins. Thus, the next-fit decreasing algorithm uses the same number of bins as a next-fit increasing algorithm.