Search Results

Documents authored by Velaj, Yllka

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.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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.31
Generalized Budgeted Submodular Set Function Maximization

Authors: Francesco Cellinese, Gianlorenzo D'Angelo, Gianpiero Monaco, and Yllka Velaj

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of 1/2(1-1/e^alpha), where alpha <= 1 is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us alpha=1- epsilon if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees alpha=1-1/e-epsilon for the general case. The gap between our approximation guarantees and the known inapproximability bounds is 1/2. We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor beta >= 1 to guarantee a 1/2(1-1/e^(alpha beta))-approximation. If we set beta=1/(alpha)ln (1/(2 epsilon)), the algorithm achieves an approximation factor of 1/2-epsilon, for any arbitrarily small epsilon>0.
Cite as

Francesco Cellinese, Gianlorenzo D'Angelo, Gianpiero Monaco, and Yllka Velaj. Generalized Budgeted Submodular Set Function Maximization. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cellinese_et_al:LIPIcs.MFCS.2018.31,
  author =	{Cellinese, Francesco and D'Angelo, Gianlorenzo and Monaco, Gianpiero and Velaj, Yllka},
  title =	{{Generalized Budgeted Submodular Set Function Maximization}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.31},
  URN =		{urn:nbn:de:0030-drops-96138},
  doi =		{10.4230/LIPIcs.MFCS.2018.31},
  annote =	{Keywords: Submodular set function, Approximation algorithms, Budgeted Maximum Coverage}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.75
Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

Authors: Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated. Starting from the work of Domingos and Richardson [Domingos et al. 2001], several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint [Kempe et al. 2003]. In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless P=NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.
Cite as

Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:LIPIcs.MFCS.2017.75,
  author =	{D'Angelo, Gianlorenzo and Severini, Lorenzo and Velaj, Yllka},
  title =	{{Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{75:1--75:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.75},
  URN =		{urn:nbn:de:0030-drops-80853},
  doi =		{10.4230/LIPIcs.MFCS.2017.75},
  annote =	{Keywords: Approximation algorithms, information diffusion, complex networks, independent cascade model, network augmentation}
}
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 About DROPS Imprint Privacy Contact