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


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
Number of pages15
ISBN (Electronic)9783959771306
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
ISSN (Print)1868-8969


Conference30th International Symposium on Algorithms and Computation, ISAAC 2019


Funding Part of this research was funded by the NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

FundersFunder number
NWO Gravitation
Nederlandse Organisatie voor Wetenschappelijk Onderzoek024.002.003


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


    Dive into the research topics of 'Approximate pricing in networks: How to boost the betweenness and revenue of a node'. Together they form a unique fingerprint.

    Cite this