Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
A note on an open-end bin packing problem
Autore:
Leung, JYT; Dror, M; Young, GH;
Indirizzi:
Univ Arizona, Dept Management Informat Syst, Tucson, AZ 85721 USA Univ Arizona Tucson AZ USA 85721 ment Informat Syst, Tucson, AZ 85721 USA Univ Nebraska, Dept Comp Sci & Engn, Lincoln, NE 68588 USA Univ Nebraska Lincoln NE USA 68588 Comp Sci & Engn, Lincoln, NE 68588 USA Chinese Univ Hong Kong, Dept Comp Sci & Engn, High Performance Comp Lab, Shatin, Hong Kong, Peoples R China Chinese Univ Hong Kong Shatin Hong Kong Peoples R China Peoples R China
Titolo Testata:
JOURNAL OF SCHEDULING
fascicolo: 4, volume: 4, anno: 2001,
pagine: 201 - 207
SICI:
1094-6136(200107/08)4:4<201:ANOAOB>2.0.ZU;2-#
Fonte:
ISI
Lingua:
ENG
Soggetto:
ALGORITHMS;
Keywords:
bin packing; complexity; approximation algorithms;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
11
Recensione:
Indirizzi per estratti:
Indirizzo: Dror, M Univ Arizona, Dept Management Informat Syst, Tucson, AZ 85721 USA Univ Arizona Tucson AZ USA 85721 ormat Syst, Tucson, AZ 85721 USA
Citazione:
J.Y.T. Leung et al., "A note on an open-end bin packing problem", J SCHED, 4(4), 2001, pp. 201-207

Abstract

We consider a variant of the classical one-dimensional bin packing problem, which we call the open-end bin packing problem. Suppose that we are givena list L = (p(1), p(2) ,.., p(n)) of n pieces, where p(j) denotes both thename and the size of the jth piece in L, and an infinite collection of infinite-capacity bins. A bin can always accommodate a piece if the bin has not yet reached a level of C or above, but it will be closed as soon as it reaches that level. Our goal is to find a packing that uses the minimum number of bins. In this article, we first show that the open-end bin packing problem remains strongly NP-hard. We then show that any online algorithm must have an asymptotic worst-case ratio of at least 2, and there is a simple online algorithm with exactly this ratio. Finally, we give an offline algorithm that is a fully polynomial approximation scheme with respect to the asymptotic worst-case ratio. Copyright (C) 2001 John Wiley & Sons, Ltd.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 22/01/20 alle ore 12:25:57