Computer Science Department
School of Computer Science, Carnegie Mellon University
Approximation Algorithms for Item Pricing
Maria-Florina Balcan, Avrim Blum
Superceded by Computer Science Technical Report CMU-CS-05-176R.
Keywords: Approximation algorithms, auction design, profit maximization, item pricing
We present approximation algorithms for a number of problems of
pricing items for sale so as to maximize seller's revenue in an
unlimited supply setting. Our main result is an
O(k)-approximation for pricing items to single-minded bidders
who each want at most k items. For the case k = 2 (where
we get a 4-approximation)
this can be viewed as the following graph
vertex pricing problem: given a graph G with valuations
ve on the edges, find prices pi for
the vertices to maximize
pi + pj.
We also improve the approximation of  from O(log m+ log n) to O(log n) for the
"highway problem" in which all desired subsets are intervals
on a line.