The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Advance Service Reservations with Heterogeneous CustomersManagement Science, 2020
- Improving refugee integration through data-driven algorithmic assignmentScience, 2018
- Randomized algorithms for online knapsack problemsTheoretical Computer Science, 2015
- Online Knapsack RevisitedTheory of Computing Systems, 2014
- Approximating the Stochastic Knapsack Problem: The Benefit of AdaptivityMathematics of Operations Research, 2008
- On the Choice-Based Linear Programming Model for Network Revenue ManagementManufacturing & Service Operations Management, 2008
- Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems2008
- Revenue Management for Parallel Flights with Customer-Choice BehaviorOperations Research, 2005
- The Dynamic and Stochastic Knapsack Problem with DeadlinesManagement Science, 1996
- Stochastic on-line knapsack problemsMathematical Programming, 1995