An \(O(\log n)\) -Competitive Posted-Price Algorithm for Online Matching on the Line
摘要
Motivated by demand-responsive parking pricing systems, we consider posted-price algorithms for the online metric matching problem. We give an \(O(\log n)\) -competitive posted-price randomized algorithm in the case that the metric space is a line. In particular, in this setting we show how to implement the ubiquitous guess-and-double technique using prices.