Summary
Imagine you have a set of servers located in different spots, and requests arrive one by one at various locations that need a nearby server assigned immediately. The challenge is to assign servers to requests in a way that keeps travel distance or cost as low as possible. The paper improves algorithms for a special kind of distance map (called a Δ-ary HST tree) where each spot connects to at most Δ branches. Their approach finds assignments almost as efficient as theoretically possible, and importantly, the efficiency does not depend on how many requests or servers there are. This improves on previous methods and approaches the best possible performance.
What this means in practice
- •For network schedulers: Assign servers to incoming requests in distributed networks more efficiently when network topology resembles a bounded branching tree structure.
- •For robotics fleet managers: Improve real-time task assignment to robots or vehicles in environments structured with hierarchical, branch-limited zones.
A theory result. No direct application yet.
Abstract
In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request must be matched to a server that was not matched to a previous request. The goal is to minimize the matching cost. For randomized algorithms with an oblivious adversary, the best known competitive ratio is obtained by embedding the metric space into an HST, and then solving the problem in the setting where the metric space is defined by the HST. Bansal et al. (Algorithmica, 2014) introduced a framework for online metric matching where one develops an algorithm in a restricted reassignment model, and then transforms this into a true online algorithm. Using this framework, they obtained an expected competitive ratio of $O(\log n)$ for HSTs; this also gives the best known competitive ratio of $O(\log^2 n)$ for general metrics. In this paper, we revisit this framework with the aim of developing new algorithms. For HSTs where each node has at most $Δ$ children, we develop an algorithm via this framework with an expected competitive ratio of $O((\log\log Δ) \cdot \log Δ)$. In particular, this ratio is independent of $n$, the number of servers/requests. It is near-optimal, as the expected competitive ratio of any algorithm is $Ω(\log Δ)$.