Variants of Classical One Dimensional Bin Packing

Authored by: János Csirik , Csanád Imreh

Handbook of Approximation Algorithms and Metaheuristics, Second Edition

Print publication date:  May  2018
Online publication date:  May  2018

Print ISBN: 9781498770118
eBook ISBN: 9781351236423
Adobe ISBN:

10.1201/9781351236423-29

 Download Chapter

 

Abstract

Few problems compete with the bin packing problem in having fascinated so many people for so long a time. Research into the classical bin packing problem dates back over four decades to the early seventies. In the original version, a list L = ( a 1 , a 2 , … , a n ) of n items, each with a size no larger than 1, is given along with an infinite supply of unit capacity bins. The goal is to pack the list into as few bins as possible so that no bin capacity is exceeded. Because the problem is NP-hard, most research has concentrated on designing fast approximation algorithms with good performance guarantees. The studies have spanned both online and offline algorithms, and have applied both combinatorial and probabilistic analysis.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.