A Short Note on Long Waiting Lists

Sebastian Stiller ()
Additional contact information
Sebastian Stiller: Technische Universität Braunschweig, Institut für Mathematische Optimierung

A chapter in Gems of Combinatorial Optimization and Graph Algorithms, 2015, pp 143-150 from Springer

Abstract: Abstract A waiting list is a commitment to pack a knapsack by a linear order—a commitment that has to be made before the capacity of the knapsack is known. The goal of this paper is to create a waiting list such that for every capacity the resulting knapsack solution is provably good. We show that there are waiting lists that yield at least 2-approximate knapsack solutions for every capacity. Their construction and the proof of their quality are arguably simple. Simple, but effective, as, in general, a factor better than 2 is impossible.

Keywords: Knapsack Problem; Small Item; Probe Item; Packing Policy; Longe Prefix (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-24971-1_14

Ordering information: This item can be ordered from
http://www.springer.com/9783319249711

DOI: 10.1007/978-3-319-24971-1_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().