A 2-Competitive Online Algorithm for Maintaining Perishable Emergency Response Kits

We introduce the Kit Update Problem, a new online optimization problem motivated by a real-world application at Doctors Without Borders. Emergency response kits -- pre-packed sets of medical items -- must be maintained in a continuously ready-to-ship state. Because many items are perishable, maintaining readiness incurs maintenance costs (manual effort) and potentially some additional expected disposal costs (due to expired or prematurely replaced items). The objective is to minimize cumulative cost over time while ensuring continuous kit operability. We show that the problem is NP-hard (indeed APX-hard) and develop a 2-approximation algorithm. We further prove that this algorithm naturally extends to a fast 2-competitive online algorithm. The resulting policy has been adopted and integrated into the organization’s operations, where it has led to reported cost reductions of 30–40% in practice. We also compare our approach with a stochastic look-ahead policy on synthetic instances calibrated to real data provided by the organization. The online algorithm achieves nearly the same performance, while requiring no forecasts, minimal computation, and exhibiting robustness to misspecification of cost parameters, making it well suited to such settings.