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 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 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 [email protected]