English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

Cross-monotonic cost sharing methods for connected facility location games

MPS-Authors
/persons/resource/persons45363

Schäfer,  Guido
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44913

Leonardi,  Stefano
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

2003-1-017
(Any fulltext), 10KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Schäfer, G., & Leonardi, S.(2003). Cross-monotonic cost sharing methods for connected facility location games (MPI-I-2003-1-017). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-6B12-7
Abstract
We present cost sharing methods for connected facility location games that are cross-monotonic, competitive, and recover a constant fraction of the cost of the constructed solution. The novelty of this paper is that we use randomized algorithms, and that we share the expected cost among the participating users. As a consequence, our cost sharing methods are simple, and achieve attractive approximation ratios for various NP-hard problems. We also provide a primal-dual cost sharing method for the connected facility location game with opening costs.