An Approximation Algorithm for Stackelberg Network Pricing

DOI10.1002/NET.20074MaRDI QIDQ6466250arXivFDO

Authors Sebastien Roch, Gilles Savard, P. Marcotte

Publication date 26 September 2004

Published in arXiv

Full work available at URL https://doi.org/10.1002/NET.20074

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Games involving graphs (91A43) Hierarchical games (including Stackelberg games) (91A65)

arXiv classification

cs.GTmath.OC

Abstract: We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $1/2lo{g}_2{m}_T+1$, where $m_T$ denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached.

This page was built for publication: An Approximation Algorithm for Stackelberg Network Pricing

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