@techreport{,
TITLE = {Cross-monotonic cost sharing methods for connected facility location games},
AUTHOR = {Sch{\"a}fer, Guido and Leonardi, Stefano},
LANGUAGE = {eng},
URL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-017},
NUMBER = {MPI-I-2003-1-017},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {2003},
DATE = {2003},
ABSTRACT = {We present cost sharing methods for connected facility location <br>games that are cross-monotonic, competitive, and recover a constant <br>fraction of the cost of the constructed solution.<br>The novelty of this paper is that we use randomized algorithms, and<br>that we share the expected cost among the participating users.<br>As a consequence, our cost sharing methods are simple, and achieve <br>attractive approximation ratios for various NP-hard problems.<br>We also provide a primal-dual cost sharing method for the connected <br>facility location game with opening costs.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}