Grigoriev,Alexander Hoesel,Stan,van Kraaij,Anton F.,van der Marc,Uetz Mustapha,Bouhtou (METEOR)
Abstract
We consider a Stackelberg pricing problem in directed networks:Tariffs (prices) have to be defined by an operator, the leader, for a subset of the arcs. Clients, the followers, choose paths to route their demand through the network selfishly and independently of each other, on the basis of minimal total cost. The problem is to find tariffs such as to maximize the operator''s revenue. We consider the case where each client takes at most one tariff arc to route the demand.The problem, which we refer to as the river tarification problem, is a special case of problems studied previously in the literature.We prove that the problem is strongly NP-hard.Moreover, we show that the polynomially solvable case of uniform tarification yields an m--approximation algorithm, and this is tight. We suggest a new type of analysis that allows to improve the result to \bigO{\log m}, whenever the input data is polynomially bounded. We furthermore derive an \bigO{m^{1-\varepsilon}}--inapproximability result for problems where the operator must serve all clients, and we discuss some polynomial special cases. Finally, a computational study with instances from France Telecom suggests that uniform pricing performs better in practice than theory would suggest.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. 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.
Publisher Info
Paper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number
009.
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
Hoesel,Stan,van & Kraaij,Anton F.,van der & Mannino,Carlo & Bouhtou,Mustapha & Oriolo,Gianpaolo, 2003.
"Polynomial cases of the tarification problem,"
Research Memoranda
063, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
[Downloadable!]
Bouhtou,Mustapha & Hoesel,Stan,van & Kraaij,Anton F.,van der & Lutton,Jean-Luc, 2003.
"Tariff optimization in Networks,"
Research Memoranda
041, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
[Downloadable!]
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)
Did you know? You can include your works in the database easily by uploading them on the Munich Personal RePEc Archive (MPRA) if you do not have access to an institutional RePEc archive.