Preemption and Free Disposal in Online Optimization

17 concepts8 papers1 proposal

In classical online and streaming optimization, algorithms are bound by a strict rule: decisions are irrevocable. When a data element arrives, the algorithm must immediately decide whether to accept it (e.g., placing it in a cache, allocating a network route, or adding it to a summary set) or reject it forever. This asymmetry creates a fundamental vulnerability. An adversarial environment can exploit this by presenting mediocre elements early on to consume all available capacity, leaving the algorithm powerless when highly valuable elements arrive later.

To bypass the severe theoretical lower bounds imposed by irrevocability, a powerful paradigm has emerged: preemption (also framed as free disposal or item removability). By allowing algorithms to "change their mind" and discard previously accepted elements to make room for superior incoming ones, systems can dynamically reallocate resources and recover from early suboptimal decisions.

The Core Mechanism: Preemptive Swapping

The fundamental challenge in online optimization with preemption is determining when a swap is justified. If an algorithm replaces an item anytime a slightly better one arrives, it risks making an infinite sequence of costly updates for negligible gains. Furthermore, in complex settings like submodular maximization—where the marginal value of an item depends on the composition of the entire selected set—naively swapping items based on isolated values can inadvertently destroy structural synergies.

To solve this, preemptive algorithms rely on threshold-based swapping strategies. Instead of accepting any marginal improvement, a new element is only allowed to evict an existing one if its value exceeds a specific mathematical threshold relative to the current solution.

[Incoming Element] ──> [Compute Marginal Gain] ──> Is Gain > Threshold?
                                                          │
                                         ┌────────────────┴────────────────┐
                                         ▼ YES                             ▼ NO
                             [Evict Suboptimal Item]               [Discard Incoming]

As demonstrated by Buchbinder et al. and later expanded in Schwartz et al., incorporating preemption into online submodular maximization fundamentally alters the competitive landscape. For unconstrained problems, the ability to revoke decisions allows algorithms to break through traditional barriers and achieve a $1/e$-competitive ratio.

In streaming environments where memory is strictly bounded, Chekuri et al. utilized this thresholding mechanism to design single-pass streaming algorithms for non-monotone submodular functions. By pairing threshold-based preemption with randomized buffering, their approach ensures that limited memory is continuously occupied by the most valuable elements encountered so far, matching approximation guarantees that were previously restricted to offline settings.

Correcting Early Errors in Data Streams

Preemption acts as an algorithmic safety net, allowing systems to hedge against the uncertainty of future data arrivals. In massive data summarization tasks, this capability is essential for maintaining high-quality outputs without storing the entire dataset.

For instance, Mitrovic et al. leveraged a two-stage submodular framework where a streaming algorithm continuously refines a representative "summary" of a dataset. The preemption logic evaluates incoming elements against the current summary; if a new element provides a significant marginal gain, it replaces an older element. This enables the algorithm to actively correct early selection errors on the fly.

Similarly, when dealing with strict capacity constraints, such as coordinate budgets in multi-agent or multi-attribute settings, eviction strategies provide a clear path to optimization. Ene et al. designed a streaming algorithm for $k$-submodular maximization that employs a structured eviction strategy. When a fixed budget is reached, the system utilizes a free disposal property to eject older, lower-value elements. This ensures that the final selection remains highly competitive, even if the highest-value elements appear at the very end of the data stream.

Minimizing Rejections and Managing Capacity

In network management and resource allocation, the primary objective is often to minimize loss rather than maximize a clear-cut profit metric. In admission control, for example, a system must decide which traffic requests to accept into a capacity-constrained network.

Azar et al. demonstrated that preemption is mathematically essential for achieving low competitive ratios when the goal is to minimize rejections. Without the ability to revoke requests, an online system can be permanently blinded by early, low-priority traffic, leading to unavoidable future rejections when high-priority requests arrive. Preemptive allocation allows the system to treat early acceptances as temporary placeholders, freeing up capacity the moment a critical request demands entry.

This concept is mirrored in the classic knapsack problem. As explored by Jez et al. in the context of the Online Multiple Knapsack Problem, item removability allows an algorithm to hedge against future uncertainty. By treating the knapsack's contents as dynamic, the algorithm can continuously optimize its total value density, ensuring that lower-value items are systematically weeded out in favor of high-profit arrivals.

A Safety Net for Learning-Augmented Algorithms

Recently, online optimization has integrated machine learning predictions to guide decision-making. While predictions can drastically improve performance when accurate, they introduce a severe vulnerability: if the predictions are flawed, a standard online algorithm will make catastrophic, irreversible decisions.

Preemption and free disposal provide an elegant solution to this problem by decoupling the utilization of predictions from the risk of predictions.

[ML Prediction] ──> [Aggressive Initial Allocation] 
                               │
                               ▼
                [Real-World Data Reveals Error]
                               │
                               ▼ (Free Disposal Safety Net)
                [Evict Low-Value Predicted Items] ──> [Allocate to True High-Value Items]

In online ad allocation, Spaeh et al. demonstrated that the free disposal model serves as a robust safety mechanism. An algorithm can aggressively follow a predictive model early in the sequence; if the predictions later prove to be inaccurate, the free disposal property allows the system to discard those poorly allocated slots and reallocate capacity to high-value items that arrive later. This design breaks past the classic $1-1/e$ competitive barrier when predictions are correct, while remaining mathematically safe if the predictions are wrong.

This resilience to prediction error also extends to structural graph problems. Berg et al. analyzed Online Minimum Spanning Trees (MST) with weight predictions. They showed that a flexible greedy strategy that adapts to real-time data by swapping edges out-performs static prediction-following approaches. By utilizing the structural slack provided by random arrival sequences, the ability to swap edges allows the algorithm to dynamically correct for initial prediction errors, ensuring robust performance regardless of prediction quality.

Key Foundational Work

Online Submodular Maximization with Preemption (2015) — contributed 3 concept elements to this direction.
Admission Control to Minimize Rejections and Online Set Cover with Repetitions (2008) — contributed 2 concept elements to this direction.
Streaming Algorithms for Submodular Function Maximization (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_element_replacement_a333d8d7,
  title = {dynamic element replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-element-replacement/rdr_a333d8d7b2cc41278e634c7d7118f17c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_dynamic_element_replacement_a333d8d7_v1,
  title = {dynamic element replacement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-element-replacement/rdr_a333d8d7b2cc41278e634c7d7118f17c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake