Pricing bridges to cross a river
AbstractWe consider a Stackelberg pricing problem in directed, uncapacitated networks. Tariffs have to be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs are assumed to be given. There are n clients, the followers, that route their demand independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by problems in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX-hard. Moreover, we show that uniform pricing yields both an mâapproximation, and a (1 + lnD)âapproximation. Here, D is upper bounded by the total demand of all clients. We furthermore discuss some polynomially solvable special cases, and present a short computational study with instances from France TÃ©lÃ©com. In addition, we consider the problem under the additional restriction that the operator must serve all clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless NP = ZPP, and we prove the existence of an nâapproximation algorithm.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht University in its series Open Access publications from Maastricht University with number urn:nbn:nl:ui:27-12046.
Date of creation: 2007
Date of revision:
Publication status: Published in Naval research logistics : an international journal (2007) v.54, p.411-420
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/Home.htm
Other versions of this item:
- Grigoriev, A & Van Hoesel, S & Van der Kraaij, AF & Spieksma, Frederik & Uetz, M & Bouhtou, M, 2005. "Pricing bridges to cross a river," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/122705, Katholieke Universiteit Leuven.
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (J.Odekerken).
If references are entirely missing, you can add them using this form.