Template-type: ReDif-Paper 1.0
Author-Name: Hoesel Stan van
Author-Name: Kraaij Anton F. van der
Author-Name: Mannino Carlo
Author-Name: Bouhtou Mustapha
Author-Name: Oriolo Gianpaolo
Author-workplace-name: METEOR
Title: Polynomial cases of the tarification problem
Abstract: We consider the problem of determining a set of optimal tariffs for an agent in a network, who owns a subset of the arcs of the network, and who wishes to maximize his revenues on this subset from a set of clients that make use of the network.The general variant of this problem is NP-hard, already with a single client. This paper introduces several new polynomially solvable special cases. An important case is the following.For multiple clients, if the number of tariff arcs is bounded from above, we can solve the problem by a polynomial number of linear programs (each of which is of polynomial size). Furthermore, we show that the parametric tarification problem and the single arc fixed charge tarification problem can be solved in polynomial time.
Keywords: Economics ; 
Series: Research Memoranda
Creation-Date: 2003
Number: 063
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:48d56eee-94bc-471e-8f6b-1249d34351b3/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 209106
Handle: RePEc:unm:umamet:2003063