A Lower Bound on the Cost Recovery of the Steiner Tree Game with Cross-Monotonic Cost Shares
Area 09 – Ingegneria industriale e dell'informazione
Tweet
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 |
| marchio editoriale: | Aracne |
| collana: | Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2004/18 |
SINTESI
