## 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 language | English |
---|---|

Title of host publication | 30th International Symposium on Algorithms and Computation (ISAAC 2019) |

Editors | Pinyan Lu, Guochuan Zhang |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 1-15 |

Number of pages | 15 |

ISBN (Electronic) | 9783959771306 |

DOIs | |

Publication status | Published - Dec 2019 |

Event | 30th International Symposium on Algorithms and Computation, ISAAC 2019 - Shanghai, China Duration: 8 Dec 2019 → 11 Dec 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 149 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 30th International Symposium on Algorithms and Computation, ISAAC 2019 |
---|---|

Country/Territory | China |

City | Shanghai |

Period | 8/12/19 → 11/12/19 |

### Funding

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

Funders | Funder number |
---|---|

NWO Gravitation | |

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 024.002.003 |

## Keywords

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