hide
Free keywords:
-
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.
