The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
We study an online knapsack problem where the items arrive sequentially and must be either immediately packed into the knapsack or irrevocably discarded. Each item has a different size and the objective is to maximize the total size of items packed. We focus on the class of randomized algorithms which initially draw a threshold from some distribution, and then pack every fitting item whose size is at least that threshold. Threshold policies satisfy many desiderata including simplicity, fairness, and incentive-alignment. We derive two optimal threshold distributions, the first of which implies a competitive ratio of 0.432 relative to the optimal offline packing, and the second of which implies a competitive ratio of 0.428 relative to the optimal fractional packing.We also consider the generalization to multiple knapsacks, where an arriving item has a different size in each knapsack and must be placed in at most one. This is equivalent to the AdWords problem where item truncation is not allowed. We derive a randomized threshold algorithm for this problem which is 0.214-competitive. We also show that any randomized algorithm for this problem cannot be more than 0.461-competitive, providing the first upper bound which is strictly less than 0.5.This online knapsack problem finds applications in many areas, like supply chain ordering, online advertising, and healthcare scheduling, refugee integration, and crowdsourcing. We show how our optimal threshold distributions can be naturally implemented in the warehouses for a Latin American chain department store. We run simulations on their large-scale order data, which demonstrate the robustness of our proposed algorithms
Year of publication: |
2019
|
---|---|
Authors: | Ma, Will ; Simchi-Levi, David ; Zhao, Jinglong |
Publisher: |
[S.l.] : SSRN |
Saved in:
freely available
Extent: | 1 Online-Ressource (37 p) |
---|---|
Type of publication: | Book / Working Paper |
Language: | English |
Notes: | Nach Informationen von SSRN wurde die ursprüngliche Fassung des Dokuments July 20, 2019 erstellt |
Other identifiers: | 10.2139/ssrn.3423199 [DOI] |
Source: | ECONIS - Online Catalogue of the ZBW |
Persistent link: https://www.econbiz.de/10014105158
Saved in favorites
Similar items by person
-
Dynamic Pricing (and Assortment) under a Static Calendar
Ma, Will, (2020)
-
Dynamic pricing (and assortment) under a static calendar
Ma, Will, (2021)
-
Design and Analysis of Switchback Experiments
Bojinov, Iavor, (2020)
- More ...