Abstract
We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with nonnegative edge costs (c_e)_{e in E}, k commodities (s_i, t_i, w_i)_{i in [k]} and a designated node u in V. Each commodity i in [k] is represented by a sourcetarget pair (s_i, t_i) in V x V and a demand w_i>0, specifying that w_i units of flow are sent from s_i to t_i along shortest s_i, t_ipaths (with respect to (c_e)_{e in 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) maxflow: maximize the total flow passing through u, and (ii) maxrevenue: 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 NPhard 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.
BibTeX  Entry
@InProceedings{brokkelkamp_et_al:LIPIcs:2019:11509,
author = {Ruben Brokkelkamp and Sven Polak and Guido Sch{\"a}fer and Yllka Velaj},
title = {{Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {13:113:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11509},
URN = {urn:nbn:de:0030drops115091},
doi = {10.4230/LIPIcs.ISAAC.2019.13},
annote = {Keywords: Network pricing, Stackelberg network pricing, betweenness centrality, revenue maximization}
}
Keywords: 

Network pricing, Stackelberg network pricing, betweenness centrality, revenue maximization 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 