Online methods match growing tree data despite uncertain growth patterns

Robust and Learned Online Matching in Growing Trees

Data Structures and AlgorithmsMachine Learning

Summary

Matching pairs in a growing tree structure is a common challenge when new parts get added over time, like leaves to a tree. The authors study how to make good pairing decisions online, even when the rules about how the tree grows are partly wrong or unknown. They develop threshold rules that adapt based on partial information and prove these rules only lose a small amount compared to an ideal method that knows the exact growth. They also provide a way to update their method over time and bound how much the uncertainty affects performance.

What this means in practice

  • For network engineers: Use robust online matching algorithms to pair nodes in dynamic tree-like network topologies with uncertain growth patterns for improved resource allocation.
  • For bioinformatics analysts: Apply adaptive matching methods to model growing biological networks such as phylogenetic trees where growth laws are only partially known.

A theory result. No direct application yet.

Authors

Marek Gałązka, Hanna Wdowicka

Abstract

We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret $O(\sqrt{n}\log^2 n)$, using $O(n^2\log n)$ arithmetic operations and $O(n)$ stored entries. The exact minimax rate remains open.