Online algorithms for a dual version of bin packing
type: Item
instance of: scholarly article
title: Online algorithms for a dual version of bin packing
zbMATH Open document ID: 0659.68069
DOI: 10.1016/0166-218X(88)90052-2
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Suppose a list \(L=(a_ 1,a_ 2,...,a_ n)\) of positive real numbers is given and that \(C\geq \max a_ i\). The dual bin packing problem consists of packing the elements of L into a maximum number of bins so that the sum of the numbers in every bin is at least C. For an online algorithm the elements of L are presented one at a time and must be packed immediately. It is shown that no online algorithm can have a performance ratio better than 1/2. This ratio can be achieved, as is shown by \textit{S. F. Assmann}, \textit{D. S. Johnson}, \textit{D. J. Kleitman} and \textit{J. Y.-T. Leung} [J. Algorithms 5, 502-525 (1984; Zbl 0556.68011)]. Furthermore an online algorithm is given which is asymptotically optimal in case the list L consists of n independent random variables which are all uniformly distributed on (0,1).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A29
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 4078808
zbMATH Keywords: optimal algorithm
zbMATH Keywords: dual bin packing
zbMATH Keywords: online algorithm
zbMATH Keywords: performance
author: János Csirik
author: Vilmos Totik
reviewed by: Walter Van Assche
MaRDI profile type: Publication
cites work: On a dual version of the one-dimensional bin packing problem
cites work: Probabilistic analysis of algorithms for dual bin packing problems
cites work: A lower bound for on-line bin packing
cites work: Q4085018
full work available at URL: 0166-218x(88)90052-2
OpenAlex ID: W2002102598
Recommended article: Online algorithms with advice for the dual bin packing problem
Recommended article: Q4535798
Recommended article: On the online bin packing problem
Recommended article: Parallel online algorithms for the Bin Packing Problem
Recommended article: Parallel online algorithms for the bin packing problem
Recommended article: Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing
Recommended article: Comparing online algorithms for bin packing problems
Recommended article: An on-line algorithm for multidimensional bin packing
Recommended article: Online algorithms for 1-space bounded 2-dimensional bin packing and square packing
Recommended article: Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing and Square Packing
description: scientific article; zbMATH DE number 4078808