Cross-monotonic cost-sharing methods for connected facility location games

We devise cost sharing methods for connected facility location games that are cross-monotonic, competitive and recover a constant fraction of the optimal cost. The novelty of this work is that we use randomized algorithms and that we share the expected cost among the participating users. We also provide a primal-dual cost sharing method for the connected facility location game with opening costs