Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Cross-monotonic cost sharing methods for connected facility location games

Schäfer, Guido and Leonardi, Stefano

MPI-I-2003-1-017. October 2003, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2003-1-017.ps117 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Sch{\"a}fer, Guido and Leonardi, Stefano},
  TITLE = {Cross-monotonic cost sharing methods for connected facility location games},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-017},
  MONTH = {October},
  YEAR = {2003},
  ISSN = {0946-011X},