CMU-CS-05-176Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-05-176
Maria-Florina Balcan, Avrim Blum July 2005
Keywords: Approximate algorithms, online optimization, profit
maximization, combinatorial auctions, single minded, unlimited supply
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 on the edges, find prices _{e}p for
the vertices to maximize
∑_{i}_{{e=(i,j):ve≥pi+pj}}
p + _{i}p.
We also improve the approximation of Guruswami et. al. from _{j}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 intervalson a line. 9 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |