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.
Cross-monotonic cost-sharing methods for connected facility location games / Leonardi, Stefano; Schäfer, Guido. - STAMPA. - 5:(2004), pp. 242-243. (Intervento presentato al convegno Proceedings of the 5th ACM Conference on Electronic Commerce,EC'04 tenutosi a New York; USA nel 17-20 May 2004).
Cross-monotonic cost-sharing methods for connected facility location games
LEONARDI, Stefano;
2004
Abstract
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2004_11573-951134.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
89.14 kB
Formato
Adobe PDF
|
89.14 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
