Knapsack Secretary with Bursty Adversary

Thomas Kesselheim, Marco Molinaro

Abstract

The random-order or secretary model is one of the most popular beyond-worst-case models for online algorithms. While it avoids the pessimism of the traditional adversarial model, in practice, we cannot expect the input to be presented in a perfectly random order. This has motivated research on "best of both worlds" algorithms or models that mix stochastic and adversarial inputs. However, achieving robustness in mixed models is notoriously difficult. In this work, we propose a random-order model with bursts of adversarial time steps. This "burstiness" is a reasonable assumption in many contexts, such as demand spikes triggered by external events. We consider the Knapsack Secretary problem within this model and design an algorithm that achieves an approximation of $1 - \tilde{O}(\Gamma/k)$, where $\Gamma$ is the number of intervals covering the adversarial steps. Our results show that this algorithm is nearly optimal even when a significant fraction of items are adversarial.

Introduction

In the classic Secretary Problem, an algorithm observes a sequence of items and must make an irrevocable decision to accept or reject each one upon arrival. Traditionally, analysis falls into two camps: the Adversarial Model, which assumes the worst possible order (often leading to a pessimistic $1/n$ competitive ratio), and the Random-Order (RO) Model, which assumes items are shuffled (allowing for a much stronger $1/e$ or even $1-\epsilon$ performance).

However, real-world data rarely adheres to either extreme. We often encounter "bursts"—sudden, non-random spikes in demand or patterns caused by external shocks. Standard RO algorithms are notoriously fragile; even a small number of strategically placed adversarial items can trick them into depleting their budget too early or waiting for high-value items that never arrive. This paper introduces the BARO (Bursty Adversary plus Random Order) model to bridge this gap, providing a framework for algorithms that are robust against localized adversarial interference.

The BARO Model and the Knapsack Secretary Problem

In the BARO model, an adversary chooses which time steps are "adversarial" and which are "random-order." To reflect realistic scenarios, these adversarial steps must be "bursty," meaning they can be covered by a limited number ($\Gamma$) of time windows.

The problem studied is the Knapsack Secretary Problem: an algorithm has a knapsack of capacity $k$. Items arrive with a value and a size in $[0, 1]$. The goal is to maximize the total value of accepted items without exceeding the capacity $k$.

The Modified Primal Algorithm

To handle the challenges of the BARO model, the authors propose a Modified Primal Algorithm. Traditional RO algorithms often solve a Linear Program (LP) based on observed data to set a threshold. The authors enhance this approach with three key mechanisms:

  1. Dynamic LP Solving: The algorithm continuously re-solves an LP at each time step $t$ based on the items seen so far.
  2. Scaled Budgets: To prevent premature budget depletion, the algorithm uses a "main inner budget" that scales linearly with time (roughly $\frac{t}{n}k$).
  3. Window-Based Constraints: This is the core innovation. The algorithm imposes "inner" and "outer" constraints that limit capacity consumption within specific time windows. These constraints act as a safeguard, ensuring that a single adversarial burst cannot "hog" the knapsack or force the algorithm into a sub-optimal state.

Analysis: The Weighted Rank Technique

Proving the efficacy of this algorithm required a new analytical framework. Standard RO proofs rely on the symmetry of permutations—the idea that any item is equally likely to appear at any time. Adversarial bursts destroy this symmetry.

The authors introduce the concept of Weighted Rank, a measure of how much the knapsack capacity would need to be scaled to include a specific item in the optimal solution. By using weighted rank, the authors can apply concentration inequalities (like Chernoff bounds) to dependent variables, allowing them to analyze the algorithm's performance even when the input sequence is partially controlled by an adversary.

Key Results

The algorithm demonstrates high performance across various levels of adversarial interference:

  • General Approximation: The algorithm achieves an approximation ratio of $1 - \tilde{O}(\Gamma/k)$.
  • Near-Optimality: When adversarial bursts are covered by $\Gamma = \sqrt{k}$ windows, the algorithm achieves a $(1 - O(\frac{\ln^2 k}{\sqrt{k}}))$-approximation. This is remarkably close to the performance of algorithms operating in a purely random environment with zero adversarial items.
  • Constant Fraction Resistance: Even if a constant fraction of the items are adversarial (where $\Gamma = \tilde{\Omega}(k)$), the algorithm still maintains a constant-factor approximation of the optimal value of the random items.

Conclusion and Future Work

This work advances the design of robust online algorithms by moving beyond the binary of "random vs. adversarial." By accounting for burstiness, the BARO model provides a more realistic playground for online optimization.

While the results for the Knapsack problem are robust, extending this logic to Packing LPs (which involve multiple constraints) remains a challenge, as the "weighted rank" concept does not yet have a clear multidimensional analogue. Additionally, future research may focus on making these algorithms "parameter-free," removing the need for the algorithm to know the window size $\ell$ or the number of bursts $\Gamma$ in advance.

Summary updated

Abstract

The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on ``best of both worlds'' (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size $k$ (e.g., available quantity of a good), and in each of the $n$ time steps an item comes with its value and size in $[0,1]$ and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of $1 - \tilde{O}(\Gamma/k)$ when the adversarial time steps can be covered by $\Gamma \ge \sqrt{k}$ intervals of size $\tilde{O}(\frac{n}{k})$. In particular, setting $\Gamma = \sqrt{k}$ gives a $(1 - O(\frac{\ln^2 k}{\sqrt{k}}))$-approximation that is resistant to up to a $\frac{\ln^2 k}{\sqrt{k}}$-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting $\Gamma = \tilde{\Omega}(k)$ gives a constant approximation that is resistant to up to a constant fraction of items being adversarial.
BibTeX
@inproceedings{kesselheim2020knapsack,
  author = {Thomas Kesselheim and Marco Molinaro},
  title = {{Knapsack Secretary with Bursty Adversary}},
  booktitle = {ICALP},
  year = {2020},
  url = {https://openreview.net/forum?id=ghuEWEPoDP},
}
Figure