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: Approximation algorithms, auction design, profit maximization, item pricing
p for
the vertices to maximize
∑_{i}_{{e=(i,j):ve≥pi+pj}}
p + _{i}p.
We also improve the approximation of [6] from _{j}O(log m+ log n) to O(log n) 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 |