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 v_e on the edges, find prices p_i for the vertices to maximize ∑_{{e=(i,j):ve≥pi+pj}} p_i + p_j. 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 [email protected]