Dynamic algorithms reduce changes in packing optimization problems
Dynamic Contention Resolution Schemes
Data Structures and Algorithms
Summary
Some problems involve picking items to fit into limited space, like filling a backpack, and these problems can change over time. The authors created a new method called Dynamic Contention Resolution Schemes (DCRSs) that helps keep solutions stable while adapting to changes. Their method limits the number of adjustments needed when the situation changes, making it efficient for complex problems like matching or packing items. This approach could make certain dynamic optimization tasks easier to manage and more predictable.
What this means in practice
- •For network schedulers: Manage dynamic resource allocation efficiently by limiting the frequency of scheduling changes for packing-like constraints in networks.
- •For supply chain planners: Maintain near-optimal item selection in changing inventory situations with fewer adjustments, especially under knapsack and matching constraints.
A theory result. No direct application yet.
Authors
Moran Feldman, Gregory Kehne, Roie Levin, Sherry Sarkar
Abstract
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs of (Online) Contention Resolution Schemes (or (O)CRSs) for low-recourse dynamic optimization and offer a variety of benefits. Similarly to their offline and online counterparts, DCRSs for different constraints can be combined to obtain DCRSs for the constraints' intersection. Furthermore, together with the Positive Body Chasing framework of Bhattacharya, Buchbinder, Levin, and Saranurak [FOCS 2023], DCRSs imply competitive recourse algorithms for fully dynamic packing problems with submodular objectives: these are algorithms that, for any input sequence, incur recourse that is itself competitive with the best possible recourse for that sequence. We show the existence of $Ω(1)$-balanced and $O(\log \mathrm{rank})$-recourse DCRSs for matroid constraints, and $Ω(1)$-balanced/$O(1)$-recourse DCRSs for matching and knapsack constraints. In particular, these yield the first non-trivial recourse bound for fully dynamic knapsack, as well as the first competitive-recourse algorithm for non-bipartite matching, and both of these apply even to monotone submodular objectives. Beyond our particular results, we view the DCRS framework as a principled step towards mechanizing the relax-and-round paradigm of approximation algorithms in the context of dynamic optimization.