In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves...In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves the worst case behavior of FFD. In fact, they proved that the inequality MFFD(L) OPT(L)+ holds for all the lists L. Their proof requires 40 pages.In this paper we give a proof for the inequality MFFD(L) OPT(L)+1, L. The proof is much simpler than theirs.展开更多
文摘In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves the worst case behavior of FFD. In fact, they proved that the inequality MFFD(L) OPT(L)+ holds for all the lists L. Their proof requires 40 pages.In this paper we give a proof for the inequality MFFD(L) OPT(L)+1, L. The proof is much simpler than theirs.
