Author name cluster

Gianlorenzo D'Angelo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Temporal Multi-Broadcast Optimization

Daniele Carnevale
Gianlorenzo D'Angelo

We introduce the D-Temporal Multi-Broadcast (D-TMB) problem, which asks for scheduling the availability of edges so that a predetermined subset of sources temporally reach all other vertices while optimizing the worst-case temporal distance D from any source. We characterize the computational complexity and approximability of D-TMB under six different definitions of temporal distance.

PDF

AAAI Conference 2025 Conference Paper

Approximating Optimal Labelings for Temporal Connectivity

Daniele Carnevale
Gianlorenzo D'Angelo
Martin Olsen

In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-step the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time a and the overall number of labels is minimum. The problem, called Minimum Aged Labeling (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases. Problem MAL has previously been proved to be NP-complete on undirected graphs and APX-hard on directed graphs. In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than O(log n) when a >= 2, unless P = NP, and a factor better than 2^[log^(1-ε) n] when a >= 3, unless NP is contained in DTIME(2^(polylog(n))), where n is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower-bounds. In particular, we show that the approximation depends on a relation between a and the diameter of the input graph. We further establish a connection with a foundational optimization problem on static graphs called Diameter Constrained Spanning Subgraph (DCSS) and show that our hardness results also apply to DCSS.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Approximation Algorithms for Connected Maximum Coverage

Gianlorenzo D'Angelo
Esmaeil Delfaraz

The Connected Budgeted maximum Coverage problem (CBC) is a combinatorial optimization problem that finds applications in path planning, wireless sensor networks, logistics, and bioinformatics. In CBC, we are given a collection of subsets S, defined over a ground set 𝑋, and an undirected graph 𝐺 = (𝑉, 𝐸), where each node is associated with a set of S. Each set in S has a different cost and each element of 𝑋 gives a different prize. The goal is to find a subcollection S′ ⊆ S such that S′ induces a connected subgraph in 𝐺, the total cost of the sets in S′ does not exceed a budget 𝐵, and the total prize of the elements covered by S′ (i. e. , Ð 𝑆∈S′ 𝑆) is maximized. The Directed rooted Connected Budgeted maximum Coverage problem (DCBC) is a generalization of CBC where the underlying graph 𝐺 is directed and in the subgraph induced by S′ in 𝐺 there must be a path from a specific node called root to any other node. These 𝑁𝑃-hard problems have been widely studied from the approximation point of view. Still, the current best algorithms achieve approximation ratios that are linear in the size of the underlying graph or depend on 𝐵. In this paper, we provide two algorithms for CBC and DCBC that guarantee approximation ratios of 𝑂 log (|𝑉 |+|𝑋 |) log |𝑋 | 𝜖2 and 𝑂 √ |𝑉 | log2 |𝑋 | 𝜖2, respectively, at the cost of a violation in the budget constraint of a factor 1 + 𝜖, where 𝜖 ∈ (0, 1]. We also improve the approximation factor for the directed budgeted rooted out-tree maximization problem, a particular case of DCBC where the prize function is additive, from 𝑂 1 𝜖2 |𝑉 |2/3 log |𝑉 | to 𝑂 1 𝜖2 |𝑉 |1/2 log2 |𝑉 |, for any 𝜖 ∈ (0, 1].

PDF

AIJ Journal 2023 Journal Article

Better bounds on the adaptivity gap of influence maximization under full-adoption feedback

Gianlorenzo D'Angelo
Debashmita Poddar
Cosimo Vinci

In the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of k nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since this definition by Kempe et al. [26]. However, most of the work focuses on the non-adaptive version of the problem where all the k seed nodes must be selected before the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observed cascade produced by the first i − 1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed under the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only work for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by n 3 + 1, where n is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from 2 e / ( e − 1 ) ≈ 3. 16 to 2 e 2 / ( e 2 − 1 ) ≈ 2. 31. Then, we consider ( β, γ ) -bounded-activation graphs, where all nodes but β influence in expectation at most γ ∈ [ 0, 1 ) neighbors each; for this class of influence graphs we show that the adaptivity gap is at most β + 1 1 − γ. Finally, we study α-bounded-degree graphs, that is the class of undirected graphs in which the sum of node degrees higher than two is at most α, and show that the adaptivity gap is upper-bounded by α + O ( 1 ); we also show that in 0-bounded-degree graphs, i. e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3 e 3 / ( e 3 − 1 ) ≈ 3. 16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.

Details DOI

AAAI Conference 2023 Conference Paper

Improving Fairness in Information Exposure by Adding Links

Ruben Becker
Gianlorenzo D'Angelo
Sajjad Ghobadi

Fairness in influence maximization has been a very active research topic recently. Most works in this context study the question of how to find seeding strategies (deterministic or probabilistic) such that nodes or communities in the network get their fair share of coverage. Different fairness criteria have been used in this context. All these works assume that the entity that is spreading the information has an inherent interest in spreading the information fairly, otherwise why would they want to use the developed fair algorithms? This assumption may however be flawed in reality -- the spreading entity may be purely efficiency-oriented. In this paper we propose to study two optimization problems with the goal to modify the network structure by adding links in such a way that efficiency-oriented information spreading becomes automatically fair. We study the proposed optimization problems both from a theoretical and experimental perspective, that is, we give several hardness and hardness of approximation results, provide efficient algorithms for some special cases, and more importantly provide heuristics for solving one of the problems in practice. In our experimental study we then first compare the proposed heuristics against each other and establish the most successful one. In a second experiment, we then show that our approach can be very successful in practice. That is, we show that already after adding a few edges to the networks the greedy algorithm that purely maximizes spread surpasses all fairness-tailored algorithms in terms of ex-post fairness. Maybe surprisingly, we even show that our approach achieves ex-post fairness values that are comparable or even better than the ex-ante fairness values of the currently most efficient algorithms that optimize ex-ante fairness.

PDF Details DOI

AAAI Conference 2023 Conference Paper

On the Cost of Demographic Parity in Influence Maximization

Ruben Becker
Gianlorenzo D'Angelo
Sajjad Ghobadi

Modeling and shaping how information spreads through a network is a major research topic in network analysis. While initially the focus has been mostly on efficiency, recently fairness criteria have been taken into account in this setting. Most work has focused on the maximin criteria however, and thus still different groups can receive very different shares of information. In this work we propose to consider fairness as a notion to be guaranteed by an algorithm rather than as a criterion to be maximized. To this end, we propose three optimization problems that aim at maximizing the overall spread while enforcing strict levels of demographic parity fairness via constraints (either ex-post or ex-ante). The level of fairness hence becomes a user choice rather than a property to be observed upon output. We study this setting from various perspectives. First, we prove that the cost of introducing demographic parity can be high in terms of both overall spread and computational complexity, i.e., the price of fairness may be unbounded for all three problems and optimal solutions are hard to compute, in some case even approximately or when fairness constraints may be violated. For one of our problems, we still design an algorithm with both constant approximation factor and fairness violation. We also give two heuristics that allow the user to choose the tolerated fairness violation. By means of an extensive experimental study, we show that our algorithms perform well in practice, that is, they achieve the best demographic parity fairness values. For certain instances we additionally even obtain an overall spread comparable to the most efficient algorithms that come without any fairness guarantee, indicating that the empirical price of fairness may actually be small when using our algorithms.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Computation and Bribery of Voting Power in Delegative Simple Games

Gianlorenzo D'Angelo
Esmaeil Delfaraz
Hugo Gilbert

Following Zhang and Grossi (AAAI 2021), we study in more depth a variant of weighted voting games in which agents’ weights are induced by a transitive support structure. This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results.

PDF

I&C Journal 2022 Journal Article

Exploiting social influence to control elections based on positional scoring rules

Federico Corò
Emilio Cruciani
Gianlorenzo D'Angelo
Stefano Ponziani

Herein, we present Linear Threshold Ranking (LTR), an extension of the Linear Threshold Model (Kempe et al. , KDD 2003). LTR models the spread of a message supporting a target candidate in a social network and how social influence affects the preferences of the voters who receive it, in elections based on positional scoring rules. The problem of election control through social influence requires finding a bounded subset of nodes to be the initial spreaders of this message to maximize the Margin of Victory of a target candidate against the most voted opponent. We prove the problem is NP-hard in LTR. By showing the equivalence of LTR with alternative stochastic processes and then exploiting submodularity, we provide a 1 3 ( 1 − 1 e ) approximation algorithm. We achieve similar results also in the destructive variation of LTR, where the message undermines a target candidate, negatively influencing the voters' preference on that candidate.

Details DOI

AAAI Conference 2021 Conference Paper

Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback

Gianlorenzo D'Angelo
Debashmita Poddar
Cosimo Vinci

In the influence maximization (IM) problem, we are given a social network and a budget 𝑘, and we look for a set of 𝑘 nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since his definition by Kempe, Kleinberg, and Tardos (2003). However, most of the work focuses on the nonadaptive version of the problem where all the 𝑘 seed nodes must be selected before that the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the 𝑖-th seed can be based on the observed cascade produced by the first 𝑖 − 1 seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only works for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by 3 √ 𝑛 + 1, where 𝑛 is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2𝑒/(𝑒 − 1) ≈ 3. 16 to 2𝑒2/(𝑒2 − 1) ≈ 2. 31. Finally, we study 𝛼-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most 𝛼, and show that the adaptivity gap is upper-bounded by √ 𝛼 + 𝑂(1). Moreover, we show that in 0-bounded graphs, i. e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3𝑒3/(𝑒3 − 1) ≈ 3. 16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.

PDF Details

AAAI Conference 2021 Conference Paper

Fairness in Influence Maximization through Randomization

Ruben Becker
Gianlorenzo D'Angelo
Sajjad Ghobadi
Hugo Gilbert

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in the area of information spread in networks. Similar to previous works like Fish et al. (WWW ’19) and Tsang et al. (IJCAI ’19), we study the maximin criterion for (group) fairness. By allowing randomized solutions, we introduce two different variants of this problem. While the original deterministic maximin problem has been shown to be inapproximable, interestingly, we show that both probabilistic variants permit approximation algorithms with a constant multiplicative factor of 1 − 1/e plus an additive arbitrarily small error due to the simulation of the information spread. For an experimental study, we provide implementations of our methods and compare the achieved fairness values to existing methods. Non-surprisingly, the ex-ante values, i. e. , minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This confirms that studying fairness via randomization is a worthwhile direction. More surprisingly, we observe that even the ex-post fairness values, i. e. , fairness values of sets sampled according to the probabilistic strategies, computed by our routines dominate over the fairness achieved by previous methods on most of the instances tested.

PDF Details

I&C Journal 2021 Journal Article

Generalized budgeted submodular set function maximization

Francesco Cellinese
Gianlorenzo D'Angelo
Gianpiero Monaco
Yllka Velaj

In the generalized budgeted submodular set function maximization problem, we are given a ground set of elements and a set of bins. Each bin has its own cost and the cost of each element depends on its associated bin. The goal is to find a subset of elements along with an associated set of bins such that the overall costs of both is at most a given budget, and the profit is maximized. We present an algorithm that guarantees a 1 2 ( 1 − 1 e α ) -approximation, where α ≤ 1 is the approximation factor of an algorithm for a sub-problem. If the costs satisfy a specific condition, we provide a polynomial-time algorithm that gives us α = 1 − ϵ, while for the general case we design an algorithm with α = 1 − 1 e − ϵ. We extend our results providing a bi-criterion approximation algorithm where we can spend an extra budget up to a factor β ≥ 1 to guarantee a 1 2 ( 1 − 1 e α β ) -approximation.

Details DOI

AAMAS Conference 2021 Conference Paper

Maximizing Influence-Based Group Shapley Centrality

Ruben Becker
Gianlorenzo D'Angelo
Hugo Gilbert

A key problem in network analysis is the influence maximization problem, which consists of finding a set S of at most k seed users in a social network, such that the spread of information from S is maximized. We investigate the problem of choosing the best set of seeds when there exists an unknown pre-existing set of seed nodes. Our work extends the one of Chen and Teng (WWW’17) who introduced the so-called Shapley centrality of a node to measure the efficiency of nodes acting as seeds within a pre-existing but unknown set of seeds. We instead consider the question: Which set of cardinality k to target in this kind of scenario? The resulting optimization problem reveals very challenging, that is, assuming common computational complexity conjectures, we obtain strong hardness of approximation results. Nevertheless, we design a greedy algorithm which achieves an approximation factor of 1−1/e k − ϵ for any ϵ > 0, showing that not all is lost in settings wherek is bounded.

PDF

AAAI Conference 2020 Conference Paper

Balancing Spreads of Influence in a Social Network

Ruben Becker
Federico Corò
Gianlorenzo D'Angelo
Hugo Gilbert

The personalization of our news consumption on social media has a tendency to reinforce our pre-existing beliefs instead of balancing our opinions. To tackle this issue, Garimella et al. (NIPS’17) modeled the spread of these viewpoints, also called campaigns, using the independent cascade model introduced by Kempe, Kleinberg and Tardos (KDD’03) and studied an optimization problem that aims to balance information exposure when two opposing campaigns propagate in a network. This paper investigates a natural generalization of this optimization problem in which μ different campaigns propagate in the network and we aim to maximize the expected number of nodes that are reached by at least ν or none of the campaigns, where μ ≥ ν ≥ 2. Following Garimella et al. , despite this general setting, we also investigate a simpliﬁed one, in which campaigns propagate in a correlated manner. While for the simpliﬁed setting, we show that the problem can be approximated within a constant factor for any constant μ and ν, for the general setting, we give reductions leading to several approximation hardness results when ν ≥ 3. For instance, assuming the gap exponential time hypothesis to hold, we obtain that the problem cannot be approximated within a factor of n−g(n) for any g(n) = o(1) where n is the number of nodes in the network. We complement our hardness results with an Ω(n−1/2 )-approximation algorithm for the general setting when ν = 3 and μ is arbitrary.

PDF Details

IJCAI Conference 2019 Conference Paper

Exploiting Social Influence to Control Elections Based on Scoring Rules

Federico Corò
Emilio Cruciani
Gianlorenzo D'Angelo
Stefano Ponziani

We consider the election control problem in social networks which consists in exploiting social influence in a network of voters to change their opinion about a target candidate with the aim of increasing his chances to win (constructive control) or lose (destructive control) the election. Previous works on this problem focus on plurality voting systems and on a influence model in which the opinion of the voters about the target candidate can only change by shifting its ranking by one position, regardless of the amount of influence that a voter receives. We introduce Linear Threshold Ranking, a natural extension of Linear Threshold Model, which models the change of opinions taking into account the amount of exercised influence. In this general model, we are able to approximate the maximum score that a target candidate can achieve up to a factor of 1-1/e by showing submodularity of the objective function. We exploit this result to provide a 1/3(1-1/e)-approximation algorithm for the constructive election control problem and a 1/2(1-1/e)-approximation ratio in the destructive scenario. The algorithm can be used in arbitrary scoring rule voting systems, including plurality rule and borda count.

PDF Details

TCS Journal 2019 Journal Article

Recommending links through influence maximization

Gianlorenzo D'Angelo
Lorenzo Severini
Yllka Velaj

The link recommendation problem consists in suggesting a set of links to the users of a social network in order to increase their social circles and the connectivity of the network. Link recommendation is extensively studied in the context of social networks and of general complex networks due to its wide range of applications. Most of the existing link recommendation methods estimate the likelihood that a link is adopted by users and recommend links that are likely to be established. However, most of such methods overlook the impact that the suggested links have on the capability of the network to spread information. Indeed, such capability is directly correlated with both the engagement of a single user and the revenue of online social networks. In this paper, we study link recommendation systems from the point of view of information diffusion. In detail, we consider the problem in which we are allowed to spend a given budget to create new links so to suggest a bounded number of possible persons to whom become friend in order to maximize the influence of a given set of nodes. We model the influence diffusion in a network with the popular Independent Cascade model.

Details DOI

IJCAI Conference 2019 Conference Paper

Recommending Links to Maximize the Influence in Social Networks

Federico Corò
Gianlorenzo D'Angelo
Yllka Velaj

Social link recommendation systems, like "People-you-may-know" on Facebook, "Who-to-follow" on Twitter, and "Suggested-Accounts" on Instagram assist the users of a social network in establishing new connections with other users. While these systems are becoming more and more important in the growth of social media, they tend to increase the popularity of users that are already popular. Indeed, since link recommenders aim at predicting users' behavior, they accelerate the creation of links that are likely to be created in the future, and, as a consequence, they reinforce social biases by suggesting few (popular) users, while giving few chances to the majority of users to build new connections and increase their popularity. In this paper we measure the popularity of a user by means of its social influence, which is its capability to influence other users' opinions, and we propose a link recommendation algorithm that evaluates the links to suggest according to their increment in social influence instead of their likelihood of being created. In detail, we give a constant factor approximation algorithm for the problem of maximizing the social influence of a given set of target users by suggesting a fixed number of new connections. We experimentally show that, with few new links and small computational time, our algorithm is able to increase by far the social influence of the target users. We compare our algorithm with several baselines and show that it is the most effective one in terms of increased influence.

PDF Details

AAMAS Conference 2019 Conference Paper

Vote For Me! Election Control via Social Influence in Arbitrary Scoring Rule Voting Systems

Federico Corò
Emilio Cruciani
Gianlorenzo D'Angelo
Stefano Ponziani

Online social networks are used to diffuse opinions and ideas among users, enabling a faster communication and a wider audience. The way in which opinions are conditioned by social interactions is usually called social influence. Social influence is extensively used during political campaigns to advertise and support candidates. We consider the problem of exploiting social influence in a network of voters to change their opinion about a target candidate with the aim of increasing his chance to win or lose the election in a wide range of voting systems. We introduce the Linear Threshold Ranking, a natural and powerful extension of the well-established Linear Threshold Model, which describes the change of opinions taking into account the amount of exercised influence. We are able to maximize the score of a target candidate up to a factor of 1 − 1/e by showing submodularity. We exploit such property to provide a 1 3 (1 − 1/e)-approximation algorithm for the constructive election control problem and a 1 2 (1 − 1/e)-approximation algorithm for the destructive control problem. The algorithm can be used in arbitrary scoring rule voting systems, including plurality rule and borda count.

PDF

MFCS Conference 2018 Conference Paper

Generalized Budgeted Submodular Set Function Maximization

Francesco Cellinese
Gianlorenzo D'Angelo
Gianpiero Monaco
Yllka Velaj

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.

Details

MFCS Conference 2017 Conference Paper

Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

Gianlorenzo D'Angelo
Lorenzo Severini
Yllka Velaj

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.

Details

TCS Journal 2016 Journal Article

Gathering of robots on anonymous grids and trees without multiplicity detection

Gianlorenzo D'Angelo
Gabriele Di Stefano
Ralf Klasing
Alfredo Navarra

The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look–Compute–Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case.

Details DOI

TCS Journal 2015 Journal Article

Finding disjoint paths in networks with star shared risk link groups

Jean-Claude Bermond
David Coudert
Gianlorenzo D'Angelo
Fatima Zahra Moataz

The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k-diverse routing problem in networks where the SRLGs are localized and satisfy the star property. This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O ( | V | 1 − ε ) for any 0 < ε < 1, where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases.

Details DOI

TCS Journal 2015 Journal Article

The minimum k-storage problem on directed graphs

Gianlorenzo D'Angelo
Daniele Diodati
Alfredo Navarra
Cristina M. Pinotti

In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P = NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O ( min ⁡ { k n 2, k 2 P } ) time, where n and P are the number of nodes and the path length of the tree [7], respectively. We improve over a previous algorithm which requires O ( k n 2 ( max ⁡ { k, d } ) d − 1 ) time, where d is the maximum out-degree of the tree [8].

Details DOI

MFCS Conference 2010 Conference Paper

Scheduling Real-Time Mixed-Criticality Jobs

Sanjoy K. Baruah
Vincenzo Bonifaci
Gianlorenzo D'Angelo
Haohan Li
Alberto Marchetti-Spaccamela
Nicole Megow
Leen Stougie

Abstract Many safety-critical embedded systems are subject to certification requirements; some systems may be required to meet multiple sets of certification requirements, from different certification authorities. Certification requirements in such “mixed-criticality” systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In this paper, we study a formal model for representing such mixed-criticality workloads. We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to two sets of certification requirements. Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former. We also show that the speedup factors are tight for these two techniques.

Details