caa a22 4500 445804998 CHVBK 20180411092529.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00453-009-9299-y doi (NATIONALLICENCE)springer-10.1007/s00453-009-9299-y The Stackelberg Minimum Spanning Tree Game [Elektronische Daten] [Jean Cardinal, Erik Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, Oren Weimann] We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min {k,1+ln b,1+ln W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. Springer Science+Business Media, LLC, 2009 Combinatorial optimization nationallicence Maximum-revenue pricing nationallicence Approximation algorithms nationallicence Spanning trees nationallicence Cardinal Jean Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut Demaine Erik MIT Computer Science and Artificial Intelligence Laboratory, 02139, Cambridge, MA, USA aut Fiorini Samuel Département de Mathématiques, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut Joret Gwenaël Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut Langerman Stefan Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut Newman Ilan Department of Computer Science, University of Haifa, 31905, Haifa, Israel aut Weimann Oren MIT Computer Science and Artificial Intelligence Laboratory, 02139, Cambridge, MA, USA aut Algorithmica Springer-Verlag 59/2(2011-02-01), 129-144 0178-4617 59:2<129 2011 59 453 https://doi.org/10.1007/s00453-009-9299-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9299-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cardinal Jean Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut NATIONALLICENCE 700 1- Demaine Erik MIT Computer Science and Artificial Intelligence Laboratory, 02139, Cambridge, MA, USA aut NATIONALLICENCE 700 1- Fiorini Samuel Département de Mathématiques, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut NATIONALLICENCE 700 1- Joret Gwenaël Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut NATIONALLICENCE 700 1- Langerman Stefan Département d'Informatique, Université Libre de Bruxelles, c.p. 212, 1050, Brussels, Belgium aut NATIONALLICENCE 700 1- Newman Ilan Department of Computer Science, University of Haifa, 31905, Haifa, Israel aut NATIONALLICENCE 700 1- Weimann Oren MIT Computer Science and Artificial Intelligence Laboratory, 02139, Cambridge, MA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/2(2011-02-01), 129-144 0178-4617 59:2<129 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 445804998 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer