Strategyproof cost-sharing mechanisms for set cover and facility location games

0.00 Avg rating—0 Votes

Article ID:	iaor20051883
Country:	Netherlands
Volume:	39
Issue:	1
Start Page Number:	11
End Page Number:	22
Publication Date:	Mar 2005
Journal:	Decision Support Systems
Authors:	Vazirani Vijay V., Devanur Nikhil R., Mihail Milena
Keywords:	location, sets

Abstract:

Strategyproof cost-sharing mechanisms, lying in the core, that recover 1/a fraction of the cost, are presented for the set cover and facility location games: a=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.

Reviews

Required fields are marked *. Your email address will not be published.