Near-optimal pricing in near-linear time

Jason D. Hartline*, Vladlen Koltun

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

42 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)422-431
Number of pages10
JournalLecture Notes in Computer Science
StatePublished - 2005
Event9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada
Duration: Aug 15 2005Aug 17 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Near-optimal pricing in near-linear time'. Together they form a unique fingerprint.

Cite this