ALCOMFT-TR-03-119

Stefano Leonardi and Guido Schäfer
Cross-Monotonic Cost-Sharing Methods for Connected Facility Location Games
Rome and MPI. Work packages 2 and 4. December 2003.

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. We also provide a primal-dual cost sharing method for the connected facility location game with opening costs.

Postscript file: ALCOMFT-TR-03-119.ps.gz (63 kb).