Approximate pricing in networks: How to boost the betweenness and revenue of a node

Ruben Brokkelkamp, Sven Polak, Guido Schäfer, Yllka Velaj

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publication30th International Symposium on Algorithms and Computation (ISAAC 2019)
EditorsPinyan Lu, Guochuan Zhang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-15
Number of pages15
ISBN (Electronic)9783959771306
DOIs
Publication statusPublished - Dec 2019
Event30th International Symposium on Algorithms and Computation, ISAAC 2019 - Shanghai, China
Duration: 8 Dec 201911 Dec 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume149
ISSN (Print)1868-8969

Conference

Conference30th International Symposium on Algorithms and Computation, ISAAC 2019
CountryChina
CityShanghai
Period8/12/1911/12/19

    Fingerprint

Keywords

  • Betweenness centrality
  • Network pricing
  • Revenue maximization
  • Stackelberg network pricing

Cite this

Brokkelkamp, R., Polak, S., Schäfer, G., & Velaj, Y. (2019). Approximate pricing in networks: How to boost the betweenness and revenue of a node. In P. Lu, & G. Zhang (Eds.), 30th International Symposium on Algorithms and Computation (ISAAC 2019) (pp. 1-15). [13] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 149). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2019.13