2 Search Results for "Brokkelkamp, Ruben"

Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.29
PACE Solver Description: tdULL

Authors: Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We describe tdULL, an algorithm for computing treedepth decompositions of minimal depth. An implementation was submitted to the exact track of PACE 2020. tdULL is a branch and bound algorithm branching on inclusion-minimal separators.
Cite as

Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep. PACE Solver Description: tdULL. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brokkelkamp_et_al:LIPIcs.IPEC.2020.29,
  author =	{Brokkelkamp, Ruben and van Veneti\"{e}, Raymond and de Vries, Mees and Westerdiep, Jan},
  title =	{{PACE Solver Description: tdULL}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{29:1--29:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.29},
  URN =		{urn:nbn:de:0030-drops-133326},
  doi =		{10.4230/LIPIcs.IPEC.2020.29},
  annote =	{Keywords: PACE 2020, treedepth, treedepth decomposition, vertex ranking, minimal separators, branch and bound}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.13
Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node

Authors: Ruben Brokkelkamp, Sven Polak, Guido Schäfer, and Yllka Velaj

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

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 (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 source-target 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_i-paths (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) 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.
Cite as

Ruben Brokkelkamp, Sven Polak, Guido Schäfer, and Yllka Velaj. Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brokkelkamp_et_al:LIPIcs.ISAAC.2019.13,
  author =	{Brokkelkamp, Ruben and Polak, Sven and Sch\"{a}fer, Guido and Velaj, Yllka},
  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:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.13},
  URN =		{urn:nbn:de:0030-drops-115091},
  doi =		{10.4230/LIPIcs.ISAAC.2019.13},
  annote =	{Keywords: Network pricing, Stackelberg network pricing, betweenness centrality, revenue maximization}
}
  • Refine by Author
  • 2 Brokkelkamp, Ruben
  • 1 Polak, Sven
  • 1 Schäfer, Guido
  • 1 Velaj, Yllka
  • 1 Westerdiep, Jan
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Network flows
  • Show More...

  • Refine by Keyword
  • 1 Network pricing
  • 1 PACE 2020
  • 1 Stackelberg network pricing
  • 1 betweenness centrality
  • 1 branch and bound
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact