### Abstract

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.

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 |

Event | 21th International Symposium on Operations Research, SOR 1996 - Technical University of Braunschweig, Braunschweig, Germany Duration: 3 Sep 1996 → 5 Sep 1996 Conference number: 21 |

### Publication series

Name | |
---|---|

Publisher | Springer |

### Conference

Conference | 21th International Symposium on Operations Research, SOR 1996 |
---|---|

Abbreviated title | SOR |

Country | Germany |

City | Braunschweig |

Period | 3/09/96 → 5/09/96 |

Other | September 3-6, 1996 |

### Keywords

- METIS-141655
- IR-85181

## Cite this

Faigle, U., & Kern, W. (1997). Packing a bin on-line to maximize the total number of items. In

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