Template-type: ReDif-Paper 1.0
Author-Name: Grigoriev,Alexander
Author-Name: Hoesel,Stan,van
Author-Name: Kraaij,Anton F.,van der
Author-Name: Marc,Uetz
Author-Name: Mustapha,Bouhtou
Author-workplace-name: METEOR
Title: Pricing Network Edges to Cross a River.
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.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2004
Number: 009
File-URL: http://arnop.unimaas.nl/show.cgi?fid=792
File-Format: application/pdf
File-Size: 322965
Handle: RePEc:unm:umamet:2004009