| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10368025 | Decision Support Systems | 2005 | 12 Pages |
Abstract
Strategyproof cost-sharing mechanisms, lying in the core, that recover 1/α fraction of the cost, are presented for the set cover and facility location games: α=O(log n) for the former and 1:861 for the latter. Our mechanisms utilize approximation algorithms for these problems based on the method of dual-fitting.
Related Topics
Physical Sciences and Engineering
Computer Science
Information Systems
Authors
Nikhil R. Devanur, Milena Mihail, Vijay V. Vazirani,