EconPapers    
Economics at your fingertips  
 

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

Pierre Lemaire (), Gerd Finke () and Nadia Brauner ()
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 () and Springer Nature Abstracting and Indexing ().

 
Page updated 2025-06-08
Handle: RePEc:spr:sprchp:978-0-387-27744-8_13