Online matching costs with uniform replenishment on the line

For m≥2 labelled supplies on [0,1], independent uniform demands and independent uniform replacement after each online match, seek a policy whose one-period root-mean-square cost has limsup at most (72000/log 2)·log(m+1)/m from every fixed inventory. After an m-period replacement phase, the same bound should hold for expected average cost including that phase at every horizon N≥2m².

Why it matters and what counts as progress

Why it matters: It asks whether a fully dynamic matching rule can attain the known lower-bound order from arbitrary initial inventories, with initialization costs included.

What counts as progress: Match the log(m)/m lower-bound order with a policy valid from every fixed inventory, including the cost of any initialization phase.

How the problem developed

12 Sept 2026 · Reported claim [1][2]
Yash Kanoria Submitted a fully dynamic one-dimensional matching policy with RMS cost O(log m/m) and a matching finite-horizon expected-cost bound for the specified uniform-replenishment model.

AI contribution

A Tight Upper Bound for Fully Dynamic Matching on the Line

Yash Kanoria

For m≥2 labeled supplies on [0,1], independent uniform demands and independent uniform replacement after each online match, the project proves a policy whose one-period root-mean-square cost, from every fixed initial inventory, has limsup at most (72000/log 2)·log(m+1)/m. After a scheduled m-period replacement phase, expected average cost including that phase obeys the same bound for every horizon N≥2m².

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (Lean 4/Mathlib kernel, Comparator and NanoDa)

Human understandingFull