Fully Dynamic Approximation Algorithms for Combinatorial Optimization

This direction is split into other directions: approximation ratio barriers in sublinear optimization, deterministic dynamic matching, approximation-efficiency trade-off. Its last version stays readable and citable here.

Version 1 of 1162 papers255 conceptsfrozen 2026-10-04

In a static world, an algorithm takes an input, processes it, and returns an answer. But real-world data—social networks, sensor streams, or ride-sharing requests—is rarely static. It is "fully dynamic," meaning elements are constantly being added and removed.

If we re-run a static algorithm from scratch every time a single edge is added to a graph, the computational cost becomes prohibitive. The goal of fully dynamic algorithms is to maintain a high-quality solution (an approximation) while spending as little time as possible on each update. This field is defined by a three-way tension between update time, approximation quality, and solution stability (recourse).

The Core Challenge: Avoiding Recomputation

The fundamental problem in dynamic settings is that a single change can theoretically ripple through an entire solution. For example, in the Maximum Independent Set (MIS) problem, adding one disk might force you to remove several others to maintain independence, which in turn might allow you to add even more disks elsewhere.

To avoid this "cascade," researchers like Sujoy Bhore, Martin Nöllenburg, and their colleagues in Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time use hierarchical structures like "nonatrees." By confining the impact of a change to a local branch of a geometric hierarchy, they can update the solution in polylogarithmic time—meaning the work required grows very slowly even as the dataset explodes in size.

Sparsification as a Maintenance Strategy

A recurring intuition across this research is that we don't need to track the entire input to maintain a good approximation. Instead, we maintain a "sparsifier"—a smaller, simpler version of the data that preserves the properties we care about.

For graph problems like Maximum Flow or Shortest Paths, this often involves "vertex sparsifiers" or "residual graph sparsification." Simon Meierhans and Rasmus Kyng demonstrate in Bootstrapping Dynamic APSP via Sparsification how to recursively compress a graph. By maintaining distances on this compressed version, they can provide distance queries in constant time while keeping update costs near-linear.

Similarly, in Incremental Approximate Maximum Flow via Residual Graph Sparsification, Gramoz Goranci and Harald Räcke show that we can bypass the complexity of exact max-flow by maintaining a sparsified version of the residual graph, allowing for much faster updates than traditional methods.

Stability and the Concept of Recourse

In many applications, such as clustering, it isn't enough for the solution to be fast; it must also be stable. If a user moves slightly, we don't want their assigned cluster center to jump to the other side of the map. This is measured as recourse: the number of changes made to the solution per update.

Sayan Bhattacharya, Silvio Lattanzi, and Nikos Parotsidis have pioneered techniques to balance this. In Fully Dynamic k-Center Clustering Made Simple, they use a hierarchy of "nested" independent sets to ensure that when a point is added or deleted, only a small, constant number of cluster centers need to be moved. This achieves near-optimal update time while maintaining a stable, constant-factor approximation.

Breaking Approximation Barriers

For years, certain problems had "barriers"—approximation ratios that seemed impossible to beat in a dynamic setting. Correlation clustering, for instance, was stuck at a 3-approximation for nearly two decades.

In Correlation Clustering Beyond the Pivot Algorithm, Soheil Behnezhad and Moses Charikar finally broke this barrier. Their algorithm, ModifiedPivot, uses local adjustments to refine the clusters. Instead of just picking a "pivot" and forming a cluster (the classic static approach), they allow for neighborhood-based moves that "clean up" the clusters as the graph evolves, achieving a 2.997-approximation in polylogarithmic time.

The Theoretical Floor

Despite these breakthroughs, there are fundamental limits to how fast these algorithms can be. Mohammadhossein Bateni and Vahab Mirrokni established in Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries that maintaining a $(2+\epsilon)$-approximation for $k$-center requires at least $\Omega(k)$ update time.

Furthermore, many problems face "conditional hardness." For example, Raghavendra Addanki and Barna Saha showed in Fully Dynamic Set Cover - Improved and Simple that under the Strong Exponential Time Hypothesis (SETH), certain update times are likely unavoidable if we want to maintain high-quality solutions. These lower bounds provide a "stop sign" for researchers, indicating when an algorithm has reached its theoretical peak efficiency.

Papers in this version

Showing 60 of 162 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fully_dynamic_approximation_algorithms_f_d8e974cf,
  title = {Fully Dynamic Approximation Algorithms for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fully-dynamic-approximation-algorithms-for-combinatorial-optimization/rdr_d8e974cf3eab4605b0c4f5ec665f38b6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_fully_dynamic_approximation_algorithms_f_d8e974cf_v1,
  title = {Fully Dynamic Approximation Algorithms for Combinatorial Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fully-dynamic-approximation-algorithms-for-combinatorial-optimization/rdr_d8e974cf3eab4605b0c4f5ec665f38b6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}