Polynomial cases of the tarification problem

Hoesel,Stan,van, Kraaij,Anton F.,van der, Carlo Mannino, Mustapha Bouhtou and Gianpaolo Oriolo
Additional contact information
Gianpaolo Oriolo: METEOR

No 63, Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization

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 (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-mac
Date: 2003
View list of references View citations in EconPapers

Downloads: (external link)
http://edocs.ub.unimaas.nl/loader/file.asp?id=852 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:umamet:2003063

Access Statistics for this paper

More papers in Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization
Series data maintained by Willy Villevoye ().