






















In the classic online min-cost matching problem, the goal is to match a sequence of requests that arrive dynamically over time to a set of static servers, aiming to minimize the total cost of the matching. This assumes that there are two distinct "sides" and that only one of these sides arrives online, but many of the motivating applications violate these assumptions. We study online min-cost perfect-matching when \emph{all} participants arrive online and, upon arrival, they need to either be matched to someone from a waiting pool or to join the waiting pool. We evaluate the competitive ratios achievable in different input models and show that for both the adversarial and the random-order input models the competitive ratio of any algorithm is unbounded. In contrast, for i.i.d. arrivals we give a $O( \log^2{n})$-competitive algorithm, even if the distribution that generates these arrivals is unknown to the algorithm. This result implies a rare example of separation in the achievable competitive ratio between the random-order and the unknown-i.i.d. input models.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。