Chasing Small Sets Optimally: Solving a 30-Year-Old Problem in Online Algorithms

Forum topic · QianXun · 2026-05-14

Summary

A forum post explains the Set Chasing Problem, a classic problem in online algorithms where a mobile server must serve requests drawn from sets of up to k possible locations while an adaptive adversary designs worst-case inputs. For thirty years, researchers knew the optimal competitive ratio had to be at least 2^k, yet the best known algorithm only achieved k·2^k, with the extra factor of k stubbornly persisting. In 2026, Christian Coester and Alexa Tudose published 'Chasing Small Sets Optimally Against Adaptive Adversaries' on arXiv, closing this 30-year gap by proving the optimal competitive ratio is exactly 2^k. The post describes the key techniques, including an 'Evolving Tree Game' framework, a doubling strategy, and recursive cost balancing, and discusses applications to cache management, distributed task scheduling, and robot path planning. It closes with a reflection on the inevitability of detours under uncertainty and the beauty of provably optimal strategies.

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

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

Just as you arrive at office A, the second order comes in: "You can deliver to lounge C, or warehouse D."

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

And there is a very nasty "dispatcher" (an adversary) who knows exactly where you are and what you will choose next. He deliberately crafts tricky orders to make you run around the maze like a headless fly.

This is the famously classic and extremely hard Set Chasing Problem in computer science.

For thirty years, top algorithm researchers were stuck on one question: if each order has at most $$k$$ candidate locations, how small a travel overhead can we guarantee?

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

The 30-Year "Exponential" Curse

In the algorithms community, the standard measure of an online algorithm (one that must make decisions without knowing the future) is the Competitive Ratio. Simply put: how many times longer is your route compared to someone with "God's view" who knew all orders in advance?

Thirty years ago, it was known that this factor must be at least $$2^k$$ (exponential).
But the best known algorithm only achieved $k \cdot 2^k$ .
That extra factor of $$k$$ was like a lump of mud stuck to your shoe — experts spent three decades trying to shake it off and failed.

The greatness of this paper: it finally removed the $$k$$ ! It proves the optimal factor is exactly $$2^k$$ .

How Not to Be Outplayed by the "Bad Dispatcher"

To deal with an adversary who can predict your behavior, you cannot simply grab immediate benefits. If you always pick the nearest point (a greedy strategy), the dispatcher will hand you a faraway point next, keeping you perpetually exhausted.

The authors invented a strategy based on an "Evolving Tree Game". Here is an intuition-level breakdown:

1. Don't stare at points, stare at the "tree": the algorithm no longer just runs around a map; it builds a continuously growing decision tree in its head. 2. Doubling strategy: the core of the solution. If you find yourself spinning in a region and your accumulated 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, it is like a $$k$$ -layer nesting doll. The algorithm recursively accounts for the cost at each layer, ensuring the adversary gains no advantage at any level.

Why This Paper Matters

If you think "food delivery" is just a joke, you are underestimating this algorithm. The Set Chasing Problem is the mother of many core problems in computer science:

Memory management: when your computer stores data in a limited cache, it is effectively chasing a set of constantly changing memory addresses.
Distributed computing: task scheduling across servers is essentially chasing minimal communication overhead over a complex network topology.
Robot path planning: a robot operating in an unknown environment is making optimal choices among many possible target locations.

This paper proves that even against the most devious, calculating adversary, there exists a strategy that is perfectly optimal at the physical limit.

Takeaway

Life is like the 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 every detour. But this paper proves with rigorous mathematics: detours are unavoidable — they are the necessary price of coping with uncertainty.

Yet with this $$2^k$$ optimal strategy, we can say with our heads held high: yes, I took a roundabout path, but I took the most reasonable detour in the entire universe.

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

*Source paper: Christian Coester and Alexa Tudose, "Chasing Small Sets Optimally Against Adaptive Adversaries", arXiv, 2026.*