Name
Abstract | ||
|---|---|---|
We consider a Stackelberg pricing problem in directed networks. Tariffs have to be defined by an operator, the leader, for a subset of the arcs, the tariff arcs. Clients, the followers, choose paths to route their demand through the network selfishly and independently of each other, on the basis of minimal cost. Assuming there exist bounds on the costs clients are willing to bear, the problem is to find tariffs such as to maximize the operator's revenue. Except for the case of a single client, no approximation algorithm is known to date for that problem. We derive the first approximation algorithms for the case of multiple clients. Our results hold for a restricted version of the problem where each client takes at most one tariff arc to route the demand. We prove that this problem is still strongly ${\mathcal NP}$-hard. Moreover, we show that uniform pricing yields both an m–approximation, and a (1 + ln D)–approximation. Here, m is the number of tariff arcs, and D is upper bounded by the total demand. We furthermore derive lower and upper bounds for the approximability of the pricing problem where the operator must serve all clients, and we discuss some polynomial special cases. A computational study with instances from France Télécom suggests that uniform pricing performs better than theory would suggest. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-31833-0_13 | Journal of Physics D |
Keywords | Field | DocType |
stackelberg pricing problem,tariff arc,uniform pricing yield,multiple client,pricing problem,uniform pricing,costs client,total demand,ln d,approximation algorithm,pricing network edge,management science,upper bound,publication,operations research | Revenue,Approximation algorithm,Mathematical optimization,Polynomial,Computer science,Tariff,Operator (computer programming),Stackelberg competition,Total revenue,Distributed computing,Bounded function | Conference |
Volume | ISSN | ISBN |
3351 | 0302-9743 | 3-540-24574-X |
Citations | PageRank | References |
10 | 1.01 | 6 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Grigoriev | 1 | 203 | 24.23 |
| Stan P.M. van Hoesel | 2 | 679 | 66.81 |
| Anton F. van der Kraaij | 3 | 19 | 1.73 |
| Marc Uetz | 4 | 456 | 43.99 |
| Mustapha Bouhtou | 5 | 76 | 10.12 |