Variants of classical one-dimensional bin packing

Edward G. Coffman, János Csirik, Joseph Leung

Research output: Chapter in Book/Report/Conference proceedingChapter

16 Scopus citations

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 three decades to the early 1970s. In the original version, a list L = (a1, a2, …, an) 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 combinatorics and probabilistic analysis.

Original languageEnglish (US)
Title of host publicationHandbook of Approximation Algorithms and Metaheuristics
PublisherCRC Press
Pages33-1-33-14
ISBN (Electronic)9781420010749
ISBN (Print)1584885505, 9781584885504
DOIs
StatePublished - Jan 1 2007

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Variants of classical one-dimensional bin packing'. Together they form a unique fingerprint.

Cite this