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 -