Pricing Online Metric Matching Algorithms on Trees
The online metrical matching problem is a well studied paradigm in online algorithms. The problem is defined on an underlying metric space with k special points called servers. Requests arrive in an online fashion on the metric space and the objective is to match requests to yet unmatched servers while minimizing the total cost of the matching.
Research into posted price algorithms for online metrical matching was initiated in Cohen at al. (2015) as part of a line of research to study the use of posted price algorithms to minimize social cost in a setting with selfish, autonomous agents instead of requests. They gave a post-price algorithm that "mimics" the log(k)-competitive algorithm for line metrics by Gupta and Lewi (2012). We investigate the post-price setting for tree metrics by characterizing the properties of post-price algorithms and giving a poly-log(k) competitive post-price algorithm on tree metrics.