Specializations and generalizations of the Stackelberg minimum spanning tree game

DOI10.1016/J.TCS.2014.11.009zbMATH Open1303.68090arXiv1407.1167OpenAlexW2099584467MaRDI QIDQ476917FDOQ476917

Authors: Luciano Gualà, Stefano Leucci, Guido Proietti, D. Bilò 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Let be given a graph $G=(V,E)$ whose edge set is partitioned into a set $R$ of emph{red} edges and a set $B$ of emph{blue} edges, and assume that red edges are weighted and form a spanning tree of $G$. Then, the emph{Stackelberg Minimum Spanning Tree} (stack) 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. stack is known to be apx-hard already when the number of distinct red weights is 2. In this paper we analyze some meaningful specializations and generalizations of stack, which shed some more light on the computational complexity of the problem. More precisely, we first show that if $G$ is restricted to be emph{complete}, then the following holds: (i) if there are only 2 distinct red 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+epsilon$, for any $epsilon>0$. Afterwards, we define a natural extension of stack, namely that in which blue edges have a non-negative emph{activation cost} associated, and it is given a global emph{activation budget} that must not be exceeded when pricing blue edges. 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+epsilon)$-approximation algorithm, for any $epsilon>0$.

Full work available at URL: https://arxiv.org/abs/1407.1167

Recommendations

• The Stackelberg Minimum Spanning Tree Game
• The Stackelberg minimum spanning tree game
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• A branch-and-cut-and-price algorithm for the Stackelberg minimum spanning tree game
• Spanning-tree games

zbMATH Keywords

minimum spanning treeStackelberg gamescommunication networksnetwork pricing games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18) Games involving graphs (91A43)

Cites Work

• Some APX-completeness results for cubic graphs
• Title not available (Why is that?)
• Stackelberg network pricing games
• An overview of Stackelberg pricing in networks
• A bilevel model of taxation and its application to optimal highway pricing
• Stackelberg network pricing is hard to approximate
• On Stackelberg pricing with computationally bounded customers
• An approximation algorithm for Stackelberg network pricing
• The Stackelberg minimum spanning tree game
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• Approximation and Online Algorithms

Cited In (8)

• On the Complexity of Stackelberg Matroid Pricing Problems
• The Stackelberg minimum spanning tree game
• Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting
• The Stackelberg Minimum Spanning Tree Game
• Computational comparisons of different formulations for the Stackelberg minimum spanning tree game
• A branch-and-cut-and-price algorithm for the Stackelberg minimum spanning tree game
• Stackelberg packing games
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs

This page was built for publication: Specializations and generalizations of the Stackelberg minimum spanning tree game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476917)