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 discuss how to give a poly-log(k) competitive post-price algorithm on tree metrics

Thesis Committee:
Anupam Gupta (Chair)
Anil Ada

Srinvasan Seshan, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

24 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu