Near-Optimal Pricing in Near-Linear Time

  • Jason D. Hartline ,
  • Vladlen Koltun

9th International Workshop Algorithms and Data Structures (WADS 2005) |

Published by Springer

论文与出版物

We present efficient approximation algorithms for a number of problems that call for computing the prices that maximize the revenue of the seller on a set of items. Algorithms for such problems enable the design of auctions and related pricing mechanisms [3]. In light of the fact that the problems we address are APX-hard in general [5], we design near-linear and near-cubic time approximation schemes under the assumption that the number of distinct items for sale is constant.