z-logo
Premium
Pricing bridges to cross a river
Author(s) -
Bouhtou Mustapha,
Grigoriev Alexander,
Hoesel Stan van,
van der Kraaij Anton F.,
Spieksma Frits C.R.,
Uetz Marc
Publication year - 2007
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20216
Subject(s) - operator (biology) , mathematical optimization , bounded function , tariff , revenue , approximation algorithm , computer science , order (exchange) , mathematical economics , mathematics , economics , finance , mathematical analysis , biochemistry , chemistry , repressor , international trade , transcription factor , gene
We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications 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 analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + ln D )‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = N P , and we prove the existence of an n ‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here