Let be given a graph G=(V,E)G=(V,E) whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and form a spanning tree of G. Then, the Stackelberg Minimum Spanning Tree (StackMST) problem is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. StackMST is known to be APX-hard already when the number of distinct red edge weights is 2. In this paper we analyze some meaningful specializations and generalizations of StackMST, which shed some more light on the computational complexity of the problem. More precisely, we first show that if G is restricted to be complete, then the following holds: (i) if there are only 2 distinct red edge weights, then the problem can be solved optimally (this contrasts with the corresponding APX-hardness of the general problem); (ii) otherwise, the problem can be approximated within 7/4+ϵ, for any ϵ>0. Afterwards, we define a natural extension of StackMST, namely that in which blue edges are associated with a non-negative activation cost, and it is given a global activation budget that can be used (and must not be exceeded) in order to activate a subset of blue edges to be priced. Here, after showing that the very same approximation ratio as that of the original problem can be achieved, we prove that if the spanning tree of red edges can be rooted so as that any root-leaf path contains at most h edges, then the problem admits a (2h+ϵ)-approximation algorithm, for any ϵ>0.

Bilo, D., Guala', L., Leucci, S., Proietti, G. (2015). Specializations and generalizations of the Stackelberg minimum spanning tree game. THEORETICAL COMPUTER SCIENCE, 562(C), 643-657 [10.1016/j.tcs.2014.11.009].

Specializations and generalizations of the Stackelberg minimum spanning tree game

GUALA', LUCIANO;
2015-01-01

Abstract

Let be given a graph G=(V,E)G=(V,E) whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and form a spanning tree of G. Then, the Stackelberg Minimum Spanning Tree (StackMST) problem is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. StackMST is known to be APX-hard already when the number of distinct red edge weights is 2. In this paper we analyze some meaningful specializations and generalizations of StackMST, which shed some more light on the computational complexity of the problem. More precisely, we first show that if G is restricted to be complete, then the following holds: (i) if there are only 2 distinct red edge weights, then the problem can be solved optimally (this contrasts with the corresponding APX-hardness of the general problem); (ii) otherwise, the problem can be approximated within 7/4+ϵ, for any ϵ>0. Afterwards, we define a natural extension of StackMST, namely that in which blue edges are associated with a non-negative activation cost, and it is given a global activation budget that can be used (and must not be exceeded) in order to activate a subset of blue edges to be priced. Here, after showing that the very same approximation ratio as that of the original problem can be achieved, we prove that if the spanning tree of red edges can be rooted so as that any root-leaf path contains at most h edges, then the problem admits a (2h+ϵ)-approximation algorithm, for any ϵ>0.
gen-2015
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Communication networks; Minimum spanning tree; Stackelberg games; Network pricing games
http://www.sciencedirect.com/science/article/pii/S0304397514008524
Bilo, D., Guala', L., Leucci, S., Proietti, G. (2015). Specializations and generalizations of the Stackelberg minimum spanning tree game. THEORETICAL COMPUTER SCIENCE, 562(C), 643-657 [10.1016/j.tcs.2014.11.009].
Bilo, D; Guala', L; Leucci, S; Proietti, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/133076
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact