Skip to main navigation Skip to search Skip to main content

On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

  • Wun Tat Chan*
  • , Prudence W.H. Wong
  • , Fencol C.C. Yung
  • *Corresponding author for this work

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

Abstract

We study the dynamic bin packing problem introduced by Coffman, Garey and Johnson [7]. This problem is a generalization of the bin packing problem in which items may arrive and depart from the packing dynamically. The main result in this paper is a lower bound of 2.5 on the achievable competitive ratio, improving the best known 2.428 lower bound [3], and revealing that packing items of restricted form like unit fractions (i.e., of size 1/k for some integer k), which can guarantee a competitive ratio 2.4985 [3], is indeed easier.

We also investigate the resource augmentation analysis on the problem where the on-line algorithm can use bins of size b (> 1) times that of the optimal off-line algorithm. An interesting result is that we prove b = 2 is both necessary and sufficient for the on-line algorithm to match the performance of the optimal off-line algorithm, i.e., achieve 1-competitiveness. Further analysis is made to give a trade-off between the bin size multiplier b and the achievable competitive ratio.

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings
EditorsDanny Z. Chen, D. T. Lee
Place of PublicationHeidelberg
PublisherSpringer Berlin Heidelberg
Pages309-319
Number of pages11
Edition1st
ISBN (Electronic)9783540369264
ISBN (Print)3540369252, 9783540369257
DOIs
Publication statusPublished - 31 Jul 2006
Event12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, China
Duration: 15 Aug 2006 → 18 Aug 2006

Publication series

NameLecture Notes in Computer Science
Volume4112
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
ISSN (Print)2512-2010
ISSN (Electronic)2512-2029
NameCOCOON: International Computing and Combinatorics Conference

Conference

Conference12th Annual International Conference on Computing and Combinatorics, COCOON 2006
Country/TerritoryTaiwan, China
CityTaipei
Period15/08/06 → 18/08/06

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

  1. SDG 9 - Industry, Innovation, and Infrastructure
    SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

  • Competitive Ratio
  • Item Size
  • Resource Augmentation
  • Harmonic Algorithm
  • Average Case Behavior

Fingerprint

Dive into the research topics of 'On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis'. Together they form a unique fingerprint.

Cite this