TY - GEN
T1 - Approximate pricing in networks
T2 - 30th International Symposium on Algorithms and Computation, ISAAC 2019
AU - Brokkelkamp, Ruben
AU - Polak, Sven
AU - Schäfer, Guido
AU - Velaj, Yllka
PY - 2019/12
Y1 - 2019/12
N2 - We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (ce)e∈E, k commodities (si, ti, wi)i∈[k] and a designated node u ∈ V . Each commodity i ∈ [k] is represented by a source-target pair (si, ti) ∈ V × V and a demand wi > 0, specifying that wi units of flow are sent from si to ti along shortest si, ti-paths (with respect to (ce)e∈E). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.
AB - We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (ce)e∈E, k commodities (si, ti, wi)i∈[k] and a designated node u ∈ V . Each commodity i ∈ [k] is represented by a source-target pair (si, ti) ∈ V × V and a demand wi > 0, specifying that wi units of flow are sent from si to ti along shortest si, ti-paths (with respect to (ce)e∈E). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.
KW - Betweenness centrality
KW - Network pricing
KW - Revenue maximization
KW - Stackelberg network pricing
UR - http://www.scopus.com/inward/record.url?scp=85076342712&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076342712&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2019.13
DO - 10.4230/LIPIcs.ISAAC.2019.13
M3 - Conference contribution
AN - SCOPUS:85076342712
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 15
BT - 30th International Symposium on Algorithms and Computation (ISAAC 2019)
A2 - Lu, Pinyan
A2 - Zhang, Guochuan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 8 December 2019 through 11 December 2019
ER -