### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 422-431 |

Number of pages | 10 |

Journal | Lecture Notes in Computer Science |

Volume | 3608 |

State | Published - Oct 24 2005 |

Event | 9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: Aug 15 2005 → Aug 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

Hartline, J. D., & Koltun, V. (2005). Near-optimal pricing in near-linear time.

*Lecture Notes in Computer Science*,*3608*, 422-431.