An approximation algorithm for Stackelberg network pricing

Medientyp: E-Artikel
Titel: An approximation algorithm for Stackelberg network pricing
Beteiligte: Roch, Sébastien; Savard, Gilles; Marcotte, Patrice
Erschienen: Wiley, 2005
Erschienen in: Networks
Sprache: Englisch
DOI: 10.1002/net.20074
ISSN: 0028-3045; 1097-0037
Schlagwörter: Computer Networks and Communications ; Hardware and Architecture ; Information Systems ; Software
Entstehung:
Anmerkungen:
Beschreibung: <jats:title>Abstract</jats:title><jats:p>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 <jats:styled-content>${{1 \over 2}\log_2 m_T+1}$<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/tex2gif-ueqn-1.gif" xlink:title="equation image" /></jats:styled-content>, where <jats:italic>m</jats:italic><jats:sub><jats:italic>T</jats:italic></jats:sub> 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. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(1), 57–67 2005</jats:p>

Nur in Feld suchen: