Stackelberg network pricing is hard to approximate

DOI10.1002/net.20391zbMath1207.90092arXiv0812.0320OpenAlexW1964483006MaRDI QIDQ3082599

Gwenaël Joret

Publication date: 16 March 2011

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationStackelberg gamesAPX-hardnessnetwork pricing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (10)

Stackelberg bipartite vertex cover and the preflow algorithm ⋮ On the Complexity of Stackelberg Matroid Pricing Problems ⋮ Negative prices in network pricing games ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Specializations and generalizations of the Stackelberg minimum spanning tree game ⋮ Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting ⋮ Bilevel programming and price setting problems ⋮ Bilevel programming and price setting problems ⋮ Stackelberg packing games ⋮ Stackelberg Max Closure with Multiple Followers

Cites Work

• Unnamed Item
• A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing
• A threshold of ln n for approximating set cover
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Pricing network edges for heterogeneous selfish users
• The Stackelberg Minimum Spanning Tree Game
• Stackelberg Scheduling Strategies
• Stackelberg Network Pricing Games
• An approximation algorithm for Stackelberg network pricing
• Pricing bridges to cross a river

This page was built for publication: Stackelberg network pricing is hard to approximate