Chasing Small Sets Optimally: 30-Year-Old Online Algorithm Problem Solved

Forum topic · QianXun · 2026-05-14

Summary

A new 2026 paper by Christian Coester and Alexa Tudose, 'Chasing Small Sets Optimally Against Adaptive Adversaries' (arXiv), resolves a three-decade-old open question in online algorithms: the set chasing problem. The problem models a service provider (like a courier in a maze) that must move to satisfy requests, where each request offers a set of up to k possible locations and the requester is an adaptive adversary who knows the algorithm's current position and future choices. For 30 years, the best known algorithms achieved a competitive ratio of k·2^k, while the lower bound was 2^k. The new paper removes the extra factor of k, proving the optimal competitive ratio is exactly 2^k. The proof introduces an 'Evolving Tree Game' framework using doubling strategies and recursive cost balancing across the k choices. Set chasing generalizes core problems in cache and memory management, distributed task scheduling, and robot path planning, making this result broadly significant for online decision-making under adversarial uncertainty.

Imagine you are a courier trapped in a maze, holding a special kind of "dynamic order list."

The rules are unusual: the customer never tells you the exact delivery location. Instead, they give you a list of alternatives. For example, the first order says: "Deliver to office A, or meeting room B." You must pick one and run there.

Just as you arrive at office A, the next order arrives: "Deliver to lounge C, or warehouse D."

Your goal: satisfy all orders while traveling the shortest possible total distance.

The twist: there is a malicious "dispatcher" (an adversary) who knows exactly where you are and what you will choose next. They deliberately issue requests designed to make you wander the maze as chaotically as possible.

This is the classic and notoriously difficult Set Chasing Problem in computer science.

For thirty years, top algorithm researchers were stuck on one question: if each order offers at most $$k$$ candidate locations, how much wasted travel can we guarantee to avoid?

Then, in 2026, Christian Coester and Alexa Tudose published a landmark paper on arXiv: "Chasing Small Sets Optimally Against Adaptive Adversaries", finally closing this 30-year open problem.

The 30-Year "Exponential" Curse

In the algorithms community, the standard measure of an online algorithm (one that must decide without knowing the future) is the Competitive Ratio: essentially, how many times longer is your route compared to someone with "god's-eye view" who knows all orders in advance?

Thirty years ago, it was known that this factor is at least $$2^k$$ (exponential).
But the best algorithm anyone could find had a factor of $k \cdot 2^k$ .
That extra factor of $$k$$ was like mud stuck to your shoe — experts spent thirty years trying to shake it off, without success.

The greatness of this paper is that it finally removes the $$k$$ : it proves the optimal factor is exactly $$2^k$$ .

How Not to Be Fooled by the "Evil Dispatcher"

The solution has a certain elegance. To deal with an adversary who can predict your behavior, you cannot simply act on immediate benefit. If you always greedily pick the nearest point, the dispatcher will immediately hand you a faraway target and keep you running.

The authors devised a strategy based on an "Evolving Tree Game." Breaking it down intuitively:

1. Focus on the tree, not the points: The algorithm no longer just runs around the map; it maintains a constantly growing decision tree in its "mind." 2. Doubling strategy: This is the core. When you find yourself circling in a region and the cost exceeds some threshold, you decisively "double" your investment and jump to a more macroscopic, more favorable position. 3. Recursive balancing: With $$k$$ candidate points, the problem nests like a $$k$$ -layer matryoshka. The algorithm recursively accounts for the cost at every layer, ensuring the adversary gains no advantage at any level.

Why This Paper Matters

If you think "food delivery" is just a joke framing, you'd be underestimating this algorithm.

The set chasing problem is the parent of many core problems in computer science:

Memory management: When your computer places data in a limited cache, it is effectively chasing a constantly changing set of memory addresses.
Distributed computing: Task scheduling across multiple servers is essentially chasing minimal communication overhead across a complex network topology.
Robot path planning: A robot operating in an unknown environment must make optimal choices among possible target locations.

The paper proves that even against the most cunning, calculating adversary, there exists a strategy that is optimal up to the theoretical limits.

To summarize:

Life is like this set chasing problem — we never know where the next order will appear.

We used to believe that with enough effort and cleverness, we could eliminate all wasted detours. But this paper proves rigorously: "wasted paths" are unavoidable; they are the necessary price of coping with uncertainty.

With this optimal $$2^k$$ strategy, however, we can hold our heads high and say: yes, I took the long way — but I took the most reasonable detour in the universe.

Finding the certain optimal strategy in an uncertain world — that is perhaps the purest expression of the beauty of algorithms.