### Abstract

Original language | Undefined |
---|---|

Title of host publication | Operations Research 1996 |

Place of Publication | Springer-Verlag, Berlin |

Publisher | Springer |

Pages | 61-65 |

Number of pages | 5 |

ISBN (Print) | 3-540-62630-1 |

DOIs | |

Publication status | Published - 14 Jan 1997 |

### Publication series

Name | |
---|---|

Publisher | Springer |

### Keywords

- METIS-141655
- IR-85181

### Cite this

*Operations Research 1996*(pp. 61-65). Springer-Verlag, Berlin: Springer. https://doi.org/10.1007/978-3-642-60744-8_12

}

*Operations Research 1996.*Springer, Springer-Verlag, Berlin, pp. 61-65. https://doi.org/10.1007/978-3-642-60744-8_12

**Packing a bin on-line to maximize the total number of items.** / Faigle, U.; Kern, Walter.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Packing a bin on-line to maximize the total number of items

AU - Faigle, U.

AU - Kern, Walter

PY - 1997/1/14

Y1 - 1997/1/14

N2 - A bin of capacity 1 and a finite sequence σ of items of sizes a1,a2,… are considered, where the items are given one by one without information about the future. An online algorithm A must irrevocably decide whether or not to put an item into the bin whenever it is presented. The goal is to maximize the number of items collected. A is f-competitive for some function f if n*(σ) ≤ f(nA(σ)) holds for all sequences σ, where n* is the (theoretical) optimum and nA the number of items collected by A. A necessary condition on f for the existence of an f-competitive (possibly randomized) online algorithm is given. On the other hand, this condition is seen to guarantee the existence of a deterministic online algorithm that is “almost” f-competitive in a well-defined sense.

AB - A bin of capacity 1 and a finite sequence σ of items of sizes a1,a2,… are considered, where the items are given one by one without information about the future. An online algorithm A must irrevocably decide whether or not to put an item into the bin whenever it is presented. The goal is to maximize the number of items collected. A is f-competitive for some function f if n*(σ) ≤ f(nA(σ)) holds for all sequences σ, where n* is the (theoretical) optimum and nA the number of items collected by A. A necessary condition on f for the existence of an f-competitive (possibly randomized) online algorithm is given. On the other hand, this condition is seen to guarantee the existence of a deterministic online algorithm that is “almost” f-competitive in a well-defined sense.

KW - METIS-141655

KW - IR-85181

U2 - 10.1007/978-3-642-60744-8_12

DO - 10.1007/978-3-642-60744-8_12

M3 - Conference contribution

SN - 3-540-62630-1

SP - 61

EP - 65

BT - Operations Research 1996

PB - Springer

CY - Springer-Verlag, Berlin

ER -