The Best-Fit Rule for Multibin Packing: An Extension of Graham's List Algorithms

Pierre Lemaire (pierre.lemaire@imag.fr), Gerd Finke (gerd.finke@imag.fr) and Nadia Brauner (nadia.brauner@imag.fr)
Additional contact information
Pierre Lemaire: Laboratoire Leibniz-IMAG
Gerd Finke: Laboratoire Leibniz-IMAG
Nadia Brauner: Laboratoire Leibniz-IMAG

A chapter in Multidisciplinary Scheduling: Theory and Applications, 2005, pp 269-286 from Springer

Abstract: Abstract In this paper, we deal with multibin packing problems. These problems are linked to multiprocessor-task scheduling as well as to bin packing problems: they consist of n objects to be packed into m bins, with each object requiring space in several bins. We propose an intuitive greedy approach (the best-fit rule), which extends the well-known list algorithms for multiprocessor scheduling, to solve the case when objects have fixed height and size. We prove that it provides a 2-approximation, and even a 4/3-approximation if the objects are sorted by non-increasing heights. Based on this method, a polynomial time approximation scheme (PTAS) will be developed.

Keywords: multibin packing; approximation algorithms; list algorithms; PTAS (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-387-27744-8_13

Ordering information: This item can be ordered from
http://www.springer.com/9780387277448

DOI: 10.1007/0-387-27744-7_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).