@inproceedings{blum2005near-optimal,
author = {Blum, Avrim and Hartline, Jason D.},
title = {Near-optimal online auctions},
booktitle = {ACM/SIAM Symposium on Discrete Algorithms (SODA)},
year = {2005},
month = {January},
abstract = {We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu [4] in which an auctioneer is selling identical items to bidders arriving one at a time. We give an auction that achieves a constant factor of the optimal profit less an O(h) additive loss term, where h is the value of the highest bid. Furthermore, this auction does not require foreknowledge of the range of bidders' valuations. On both counts, this answers open questions from [4, 5]. We further improve on the results from [5] for the online posted-price problem by reducing their additive loss term from O(h log h log log h) to O(h log log h). Finally, we define the notion of an (offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori indistinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes.},
publisher = {ACM/SIAM},
url = {http://approjects.co.za/?big=en-us/research/publication/near-optimal-online-auctions/},
pages = {1156-1163},
edition = {ACM/SIAM Symposium on Discrete Algorithms (SODA)},
}