首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Dynamic Pricing of Servers on Trees
  • 本地全文:下载
  • 作者:Ilan Reuven Cohen ; Alon Eden ; Amos Fiat
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:145
  • 页码:1-22
  • DOI:10.4230/LIPIcs.APPROX-RANDOM.2019.10
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server. This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.
  • 关键词:Online algorithms; Online mechanisms; k-server problem; Online pricing
国家哲学社会科学文献中心版权所有