An Approximation Algorithm for Stackelberg Network Pricing
<|reference_start|>An Approximation Algorithm for Stackelberg Network Pricing: 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/2}\log_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.<|reference_end|>
@article{roch2004an,
    title={An Approximation Algorithm for Stackelberg Network Pricing},
    author={S. Roch, P. Marcotte, G. Savard},
    journal={arXiv preprint arXiv:cs/0409054},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0409054},
    primaryClass={cs.GT math.OC}
}