A Lower Bound on the Cost Recovery of the Steiner Tree Game with Cross-Monotonic Cost Shares
5,00 €
     
SINTESI
In this article it is proven that no cross-monotonic cost-sharing method can guarantee a recovery of more than 12 of the cost of the computed tree in the Steiner Tree game. Hence the algorithms described by Jain and Vazirani [3] (Steiner Tree game) and by K¨onemann et al. [2] (Steiner Forest game) are the best possible. This is accomplished by modifying an instance used in the paper by Immorlica et al. [1] for the Facility Location game, and bounding the expected value of the sum of the cost shares.
pagine: 8
formato: 17 x 24
ISBN: 978-88-7999-872-7
data pubblicazione: Gennaio 2006
editore: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2004/18
SINTESI
Informativa      Aracneeditrice.it si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più
Accetto