Near-optimal pricing in near-linear time

Jason D. Hartline; Vladlen Koltun

doi:10.1007/11534273_37

Near-optimal pricing in near-linear time

Jason D. Hartline^*, Vladlen Koltun

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Conference article › peer-review

55 Scopus citations

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
DOIs	https://doi.org/10.1007/11534273_37
State	Published - 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
General Computer Science

Access to Document

10.1007/11534273_37

Cite this

@article{3233f9797f7849199701915a89de621a,

title = "Near-optimal pricing in near-linear time",

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.",

author = "Hartline, {Jason D.} and Vladlen Koltun",

year = "2005",

doi = "10.1007/11534273_37",

language = "English (US)",

volume = "3608",

pages = "422--431",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "9th International Workshop on Algorithms and Data Structures, WADS 2005 ; Conference date: 15-08-2005 Through 17-08-2005",

}

TY - JOUR

T1 - Near-optimal pricing in near-linear time

AU - Hartline, Jason D.

AU - Koltun, Vladlen

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26844449083&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26844449083&partnerID=8YFLogxK

U2 - 10.1007/11534273_37

DO - 10.1007/11534273_37

M3 - Conference article

AN - SCOPUS:26844449083

SN - 0302-9743

VL - 3608

SP - 422

EP - 431

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 9th International Workshop on Algorithms and Data Structures, WADS 2005

Y2 - 15 August 2005 through 17 August 2005

ER -

Near-optimal pricing in near-linear time

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this