The Stackelberg minimum spanning tree game

DOI10.1007/s00453-009-9299-yzbMath1207.90091arXivcs/0703019OpenAlexW3101753513MaRDI QIDQ627533

Jean Cardinal, Ilan Newman, Gwenaël Joret, Oren Weimann, Erik D. Demaine, Stefan Langerman, Samuel Fiorini

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsspanning treesmaximum-revenue pricing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hierarchical games (including Stackelberg games) (91A65) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (21)

Stackelberg bipartite vertex cover and the preflow algorithm ⋮ On the Complexity of Stackelberg Matroid Pricing Problems ⋮ Backward induction algorithm for a class of closed-loop Stackelberg games ⋮ A branch-and-cut-and-price algorithm for the Stackelberg minimum spanning tree game ⋮ Negative prices in network pricing games ⋮ Computational comparisons of different formulations for the Stackelberg minimum spanning tree game ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ On bilevel machine scheduling problems ⋮ The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs ⋮ Specializations and generalizations of the Stackelberg minimum spanning tree game ⋮ Spanning-Tree Games. ⋮ On stackelberg pricing with computationally bounded customers ⋮ Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting ⋮ On the Stackelberg knapsack game ⋮ Bilevel programming and price setting problems ⋮ Bilevel programming and price setting problems ⋮ Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments ⋮ Stackelberg packing games ⋮ Network investment games with Wardrop followers ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography ⋮ Stackelberg Max Closure with Multiple Followers

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• An overview of Stackelberg pricing in networks
• A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• PRICING GEOMETRIC TRANSPORTATION NETWORKS
• How to Sell a Graph: Guidelines for Graph Retailers
• Single-minded unlimited supply pricing on sparse instances
• The Stackelberg Minimum Spanning Tree Game
• Stackelberg Network Pricing Games
• An approximation algorithm for Stackelberg network pricing
• Algorithms and Data Structures
• Pricing bridges to cross a river

This page was built for publication: The Stackelberg minimum spanning tree game