Computer Science Department
School of Computer Science, Carnegie Mellon University


Approximation Algorithms for Item Pricing

Maria-Florina Balcan, Avrim Blum

July 2005

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

Keywords: Approximate algorithms, online optimization, profit maximization, combinatorial auctions, single minded, unlimited supply

We present approximation algorithms and online 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 algorithm for pricing items to single-minded bidders who each want at most k items. This improves over recent independent work of Briest and Krysta who achieve an O2) bound. For the case k = 2, where we get a 4-approximation, this can be viewed as the following graph vertex pricing problem: given a (multi)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 Guruswami et. al. from O(log m+ log n) to O(log n), where m is the number of bidders and n is the number of items, 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