Pricing network edges to cross a river

G Persiano (Editor), A. Grigoriev, R Solis-Oba (Editor), S. van Hoesel, A. van der Kraaij, Marc Jochen Uetz, M. Bouhtou

Research output: Contribution to conferencePaperAcademicpeer-review

15 Citations (Scopus)

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 operators 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 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.
Original languageUndefined
Pages140-153
Number of pages14
DOIs
Publication statusPublished - Feb 2005

Keywords

  • IR-62220
  • EWI-12128

Cite this

Persiano, G. (Ed.), Grigoriev, A., Solis-Oba, R. (Ed.), van Hoesel, S., van der Kraaij, A., Uetz, M. J., & Bouhtou, M. (2005). Pricing network edges to cross a river. 140-153. https://doi.org/10.1007/b106130
Persiano, G (Editor) ; Grigoriev, A. ; Solis-Oba, R (Editor) ; van Hoesel, S. ; van der Kraaij, A. ; Uetz, Marc Jochen ; Bouhtou, M. / Pricing network edges to cross a river. 14 p.
@conference{5b3c7f3396b44cfea4d5ba6570217d82,
title = "Pricing network edges to cross a river",
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 operators 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 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{\'e}l{\'e}com suggests that uniform pricing performs better than theory would suggest.",
keywords = "IR-62220, EWI-12128",
author = "G Persiano and A. Grigoriev and R Solis-Oba and {van Hoesel}, S. and {van der Kraaij}, A. and Uetz, {Marc Jochen} and M. Bouhtou",
year = "2005",
month = "2",
doi = "10.1007/b106130",
language = "Undefined",
pages = "140--153",

}

Persiano, G (ed.), Grigoriev, A, Solis-Oba, R (ed.), van Hoesel, S, van der Kraaij, A, Uetz, MJ & Bouhtou, M 2005, 'Pricing network edges to cross a river' pp. 140-153. https://doi.org/10.1007/b106130

Pricing network edges to cross a river. / Persiano, G (Editor); Grigoriev, A.; Solis-Oba, R (Editor); van Hoesel, S.; van der Kraaij, A.; Uetz, Marc Jochen; Bouhtou, M.

2005. 140-153.

Research output: Contribution to conferencePaperAcademicpeer-review

TY - CONF

T1 - Pricing network edges to cross a river

AU - Grigoriev, A.

AU - van Hoesel, S.

AU - van der Kraaij, A.

AU - Uetz, Marc Jochen

AU - Bouhtou, M.

A2 - Persiano, G

A2 - Solis-Oba, R

PY - 2005/2

Y1 - 2005/2

N2 - 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 operators 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 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.

AB - 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 operators 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 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.

KW - IR-62220

KW - EWI-12128

U2 - 10.1007/b106130

DO - 10.1007/b106130

M3 - Paper

SP - 140

EP - 153

ER -

Persiano G, (ed.), Grigoriev A, Solis-Oba R, (ed.), van Hoesel S, van der Kraaij A, Uetz MJ et al. Pricing network edges to cross a river. 2005. https://doi.org/10.1007/b106130