CMU-CS-05-176
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-05-176

Approximation Algorithms for Item Pricing

Maria-Florina Balcan, Avrim Blum

July 2005

Superceded by Computer Science Technical Report CMU-CS-05-176R. CMU-CS-05-176.ps
CMU-CS-05-176.pdf


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 ∑{e=(i,j):ve≥pi+pj} pi + pj. We also improve the approximation of [6] from O(log m+ log n) to O(log n) for the "highway problem" in which all desired subsets are intervals
on a line.

9 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu