Federated learning (FL) has emerged as a transformative paradigm enabling collaborative machine learning without centralizing data, preserving client privacy. This is particularly relevant in the context of edge computing, where the proliferation of Internet of Things devices has led to an explosion of data at the network’s edge. These IoT devices, often battery-powered, are limited by their energy capacities, which pose significant challenges for the adoption of FL in such environments. In this paper, we introduce BatteryFL, a novel framework that coordinates battery-aware clients through FL to maximize their contribution to the global model while ensuring a fair distribution of energy consumption across the clients without compromising accuracy. BatteryFL incorporates an innovative data collection algorithm that prioritizes data diversity to minimize battery usage and a sample relevance-based algorithm to select optimal data for training. We also integrate a client selection strategy into the framework to optimize training loss and fairness (based on the battery energy of the clients) simultaneously. Along with a theoretical analysis, we experimentally demonstrate that BatteryFL significantly improves the energy efficiency of FL, prolonging the data collection and the contributions of the clients.

The UAV market has experienced significant growth, with an expanding range of applications. However, the reliance of UAV missions on GNSS makes them vulnerable to attacks, particularly GNSS spoofing and jamming, which can cause mission failure or even physical damage. To mitigate this risk, we propose a lightweight fleet protocol designed to ensure that drones can complete their missions securely, even when under attack. Our system utilizes intra-fleet communication and Received Signal Strength Indicator (RSSI) measurements for positioning, enabling the fleet to maintain formation and reach its destination even under GNSS attacks, or in a GNSS compromised scenario, thus avoiding its vulnerabilities. The proposed protocol was evaluated through extensive simulations using NS-3. The results reveal that the proposed protocol achieves a high mission success rate, reaching 100 % in most single-attack scenarios, and demonstrates robust attack identification even when multiple drones are attacked or compromised. The average attack detection delay was measured at 300 milliseconds for single-attacker scenarios, while the RSSI table was updated every 50 to 55 milliseconds, ensuring data freshness. These findings highlight the potential of our solution to improve the resilience of UAV swarms in GNSS-compromised environments.

Unmanned Aerial Vehicles (UAVs) operate under strict Size, Weight, and Power (SWaP) constraints, making traditional security mechanisms impractical. Many existing authentication protocols rely on centralized infrastructure, introducing Single Points of Failure (SPoF) and requiring continuous connectivity-unsuitable for decentralized UAV swarms. Moreover, few support the secure addition of new UAVs post-deployment. We propose SPARKS, a lightweight, serverless authentication protocol tailored for UAV swarms. Unlike prior approaches, SPARKS enables dynamic, mutual UAV-to-UAV authentication without central authorities, using only XOR operations, cryptographic hashes, and Physical Unclonable Functions (PUFs). It provides resilience against common attacks, including impersonation and device capture. Security is formally verified using the Tamarin Prover, and performance is validated on resourceconstrained devices (Raspberry Pi 4 and 5). Results demonstrate that SPARKS achieves strong security guarantees and practical efficiency, making it a compelling solution for secure, flexible UAV swarm coordination.

In the eternal vertex cover problem, mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on its edges by moving to neighboring vertices. The eternal vertex cover problem consists of determining the minimum number of necessary guards. Motivated by previous literature, we study the vertex cover and eternal vertex cover problems on regular grids when passing from infinite to finite versions of the same graphs, and we provide either coinciding or very tight lower and upper bounds on the number of necessary guards. To this aim, we generalize the notions of minimum vertex covers and minimum eternal vertex cover in order to be well-defined for infinite grids.

Unmanned aerial vehicles (UAVs) are crucial in various civilian applications, especially in Beyond Visual Line of Sight (BVLoS) operations. However, current regulations restrict BVLoS flights to specific corridors for safety reasons. This paper investigates the Drone Path Scheduling Problem (DPSP) whose goal is to assign time slots to each UAV by considering the corridors that UAVs need to traverse, and their starting time slot, in order to reach their destination such that the maximum slot for which all UAVs accomplished their mission is minimized. Time slots guarantee that each UAV accesses a corridor at a unique time, preventing multiple UAVs from using the same corridor simultaneously. We propose the Rec and the Heap-Based algorithms for unidirectional paths, demonstrating their optimality. For bidirectional paths, we offer sub-optimal solutions using Heap-Based and a 2-approximation algorithm called Bi-Alg. Furthermore, we present an Integer Linear Programming (ILP) formulation to optimally solve DPSP on unidirectional and bidirectional paths. Performance evaluations show the efficacy and scalability of our proposed algorithms compared to the ILP formulation.

One of the most valuable and promising applications for Unmanned aerial vehicles (UAVs) is in natural disaster management, where these aircraft can operate autonomously without any need for human intervention during their flights. In this paper, we foster the interface of Operational Research with computer science in general and sensor networking in particular by focusing on managing a post-disaster emergency scenario where the use of a fleet of UAVs helps rescue teams identify people needing help inside an affected area. We model this situation as an original graph theoretical problem called Multi-Depot Multi-Trip Vehicle Routing Problem with Total Completion Time minimization (MDMT-VRP-TCT). The main novelty of the MDMT-VRP-TCT is the combination of the following three features: multi-depot, multi-trip, and completion time minimization. We propose a mixed-integer linear programming (MILP) formulation, develop a matheuristic framework to address large instances, and present an extended set of experiments to test the performance of the proposed matheuristic: first, we compare the matheuristic with the MILP formulation on a set of small instances (up to 30 nodes); then, we compare our matheuristic with two heuristics from networking literature, showing that it outperforms the existing algorithms.

Drones have become increasingly popular in a variety of fields, including agriculture, emergency response, and package delivery. However, most drone operations are currently limited to within Visual Line of Sight () due to safety concerns. Flying drones Beyond Visual Line of Sight () broadens to new challenges and opportunities, but also requires new technologies and regulatory frameworks to ensure that the drone is constantly under the control of a remote operator. In this work, we propose a novel graph-based multi-layer framework that closely resembles real-world scenarios and challenges in order to plan drone operations. Our framework includes layers of constraints such as ground risk, cellular network infrastructure, and obstacles, at different heights. From the multi-layer structure, a graph is constructed whose edges are weighted with a dependability score that takes into account the information of the layers, allowing efficient path planning of missions, using algorithms such as Dijkstra’s. Since the built graph can be really large, we also propose lighter graph-based corridors by considering only a limited portion of the original graph. Through extensive experimental evaluation on a real dataset, we demonstrate the effectiveness of our framework in solving the (), which can be efficiently solved by applying the Dijkstra’s algorithm.

The use of drones for collecting information and detecting bugs in orchards covered by nets is a challenging problem. The nets help in reducing pest damage, but they also constrain the drone’s flight path, making it longer and more complex. To address this issue, we model the orchard as an aisle-graph, a regular data structure that represents consecutive aisles where trees are arranged in straight lines. The drone flies close to the trees and takes pictures at specific positions for monitoring the presence of bugs, but its energy is limited, so it can only visit a subset of positions. To tackle this challenge, we introduce the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the orienteering problem, where likely infested locations are prioritized by assigning them a larger profit. Additionally, the drone’s movements have a cost in terms of energy, and the objective is to plan a drone’s route in the most profitable locations under a given drone’s battery. We show that SOAP can be optimally solved in polynomial time, but for larger orchards/instances, we propose faster approximation and heuristic algorithms. Finally, we evaluate the algorithms on synthetic and real datasets to demonstrate their effectiveness and efficiency.

In this work, we investigate the impact of the wind in a drone-based delivery system. For the first time, to the best of our knowledge, we adapt the trajectory of the drone to the wind. We consider a truck-drone tandem delivery system. The drone actively reacts to the wind adopting the “most tailwind” trajectory available between the truck’s path and the delivery. The truck moves on a predefined route and carries the drone close to the delivery point. We propose the Minimum-energy Drone-trajectory Problem (MDP) which aims, when the wind affects the delivery area, at planning minimum-energy trajectories for the drone to serve the customers starting from and returning to the truck. We then propose two algorithms that optimally solve MDP under two different routes of the truck. We also analytically study the feasibility of sending drones with limited battery to deliver packages. Finally, we first numerically compare our algorithms on randomly generated synthetic and real data, and then we evaluate our model simulating the drone’s flight in the BlueSky simulator.

In this paper, we consider the problem of using a drone to collect information within orchards in order to detect bugs. An orchard can be modeled as an aisle-graph, which is a regular data structure formed by consecutive aisles where trees are arranged in a straight line. For monitoring the presence of bugs, a drone flies close to the trees and takes videos and/or pictures that will be analyzed offline. As the drone’s energy is limited, only a subset of locations in the orchard can be visited with a fully charged battery. Those places that are most likely to be infested should be selected to promptly detect the parasite. We study the budgeted constrained position selection problem in the orchard from an algorithmic point of view. We present the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the well-known orienteering problem where the finite resource is the drone’s battery. We first show that SOAP can be optimally solved for aisle-graphs in polynomial time. However, the optimal solution is not efficient for large orchards. Then, we propose two efficient heuristics that work even for large (orchard) instances. After a thorough analysis of the proposed solutions, we evaluate their performance by simulation experiments on both synthetic and real data sets.

In the era of a data-driven society with the ubiquity of Internet of Things (IoT) devices storing large amounts of data localized at different places, distributed learning has gained a lot of traction, however, assuming independent and identically distributed data (iid) across the devices. While relaxing this assumption that anyway does not hold in reality due to the heterogeneous nature of devices, federated learning (FL) has emerged as a privacy-preserving solution to train a collaborative model over non-iid data distributed across a massive number of devices. However, the appearance of malicious devices (attackers), who intend to corrupt the FL model, is inevitable due to unrestricted participation. In this work, we aim to identify such attackers and mitigate their impact on the model, essentially under a setting of bidirectional label flipping attacks with collusion. We propose two graph theoretic algorithms, based on Minimum Spanning Tree and k-Densest graph, by leveraging correlations between local models. Our FL model can nullify the influence of attackers even when they are up to 70% of all the clients whereas prior works could not afford more than 50% of clients as attackers. The effectiveness of our algorithms is ascertained through experiments on two benchmark datasets, namely MNIST and Fashion-MNIST, with overwhelming attackers. We establish the superiority of our algorithms over the existing ones using accuracy, attack success rate, and early detection round.

In this article, we study the orienteering aisle-graph single-access problem (OASP), a variant of the orienteering problem for a robot moving in a so-called single-access aisle graph, i.e., a graph consisting of a set of rows that can be accessed from one side only. Aisle graphs model, among others, vineyards or warehouses. Each aisle-graph vertex is associated with a reward that a robot obtains when it visits the vertex itself. As the energy of the robot is limited, only a subset of vertices can be visited with a fully charged battery. The objective is to maximize the total reward collected by the robot with a battery charge. We first propose an optimal algorithm that solves the OASP in O (m 2n 2) time for aisle graphs with a single access consisting of m rows, each with n vertices. With the goal of designing faster solutions, we propose four greedy suboptimal algorithms that run in at most O(mn\(m + n)) time. For two of them, we guarantee an approximation ratio of 1 2(1-1 e), where e is the base of the natural logarithm, on the total reward by exploiting the well-known submodularity property. Experimentally, we show that these algorithms collect more than 80% of the optimal reward.

The use of drones can be a valuable solution for the problem of delivering goods for many reasons. In fact, they can be efficiently employed in time-critical situations when there is a traffic jam on the roads, to serve customers in hard-to-reach places, or simply to expand the business. However, due to limited battery capacities and the fact that drones can serve a single customer at a time, a drone-based delivery system (DBDS) aims to minimize the drones’ energy usage for completing a route from the depot to the customer and go back to the depot for new deliveries. In general, the shortest delivery route could not be the optimal choice since external factors like the wind (which varies with time) can affect energy consumption. Previous work has mainly considered simplified DBDSs assuming architectures with a single drone and with static costs on paths. Moreover, in these non-centralized architectures, the drones themselves compute the routes on the fly employing their onboard processing resources, making this choice costly. In this paper we develop a centralized system for computing energy-efficient time-varying routes for drones in a multi-depot multi-drone delivery system. Specifically, we propose a novel centralized parallel algorithm called Parallel Shortest Route Update (PSRU) that, over time, updates the drones’ delivery routes avoiding the whole recomputation from scratch. A comprehensive evaluation proves that PSRU is up to 4. 5x faster than the state-of-the-art algorithms.

In this paper, we study the feasibility of sending drones to deliver goods from a depot to a customer by solving what we call the Mission-Feasibility Problem (MFP). Due to payload constraints, the drone can serve only one customer at a time. To this end, we propose a novel framework based on time-dependent cost graphs to properly model the MFP and tackle the delivery dynamics. When the drone moves in the delivery area, the global wind may change thereby affecting the drone's energy consumption, which in turn can increase or decrease. This issue is addressed by designing three algorithms, namely: (i) compute the route of minimum energy once, at the beginning of the mission, (ii) dynamically reconsider the most convenient trip towards the destination, and (iii) dynamically select only the best local choice. We evaluate the performance of our algorithms on both synthetic and real-world data. The changes in the drone's energy consumption are reflected by changes in the cost of the edges of the graphs. The algorithms receive the new costs every time the drone flies over a new vertex, and they have no full knowledge in advance of the weights. We compare them in terms of the percentage of missions that are completed with success (the drone delivers the goods and comes back to the depot), with delivered (the drone delivers the goods but cannot come back to the depot), and with failure (the drone neither delivers the goods nor comes back to the depot).

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 to predict user behavior, they accelerate the creation of links that are likely to be created in the future and, consequently, reinforce social bias by suggesting few (popular) users, giving few chances to most users to create new connections and increase their popularity. In this article, we measure the popularity of a user by means of her social influence, which is her 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 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 considering the Linear Threshold model as model for diffusion. 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.

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 simplified one, in which campaigns propagate in a correlated manner. While for the simplified 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.

In this paper, we study the Orienteering Aislegraphs Single-column Problem (OASP), which is a variant of the route planning problem for an entity/robot moving along a specific aisle-graph consisting of a set of rows connected via just one column at one endpoint of the rows. Such constrained aislegraph may model, for instance, a vineyard or warehouse, where each vertex is assigned with a reward that a robot gains when visiting it for accomplishing a task. As the robot is energy limited, it must visit a subset of vertices before going back to the depot for recharging, while maximizing the total reward gained. It is known that the OASP for constrained aisle-graphs composed by m rows of length n is polynomially solvable in O(m2n2) time, which can be prohibitive for graphs of large dimensions. With the goal of designing more time efficient solutions, we propose four algorithms that iteratively build the solution in a greedy manner. These solutions take at most O(mn (m + n)) time, thus improving the optimal solution by a factor of n. Experimentally, we show that these algorithms collect more than 80% of the optimum reward. For two of them, we also guarantee an approximation ratio of 1/2(1 - 1/e)on the reward function by exploiting the submodularity property, where e is the base of the natural logarithm.

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be intractable. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.

The recent push towards test automation and test-driven development continues to scale up the dimensions of test code that needs to be maintained, analysed, and processed side-by-side with production code. As a consequence, on the one side regression testing techniques, e.g., for test suite prioritization or test case selection, capable to handle such large-scale test suites become indispensable; on the other side, as test code exposes own characteristics, specific techniques for its analysis and refactoring are actively sought. We present JTeC, a large-scale dataset of test cases that researchers can use for benchmarking the above techniques or any other type of tool expressly targeting test code. JTeC collects more than 2.5M test classes belonging to 31K+ GitHub projects and summing up to more than 430 Million SLOCs of ready-to-use real-world test code.

We study the possibility of using drones to implement an automated picking system in a warehouse. We imagine a warehouse divided into two contiguous areas: in one area, the drone moves according to the Euclidean distance, while in the other area, the drone moves according to the Manhattan distance. For each customer-order (CO), the automated picking system is in charge of gathering the items requested in the CO to a predefined location where the cart of the drone is positioned. For each item of the order, the drone flies to the location where the item is stored, grasps it, and brings it back to its cart. Our goal is to find the position of the drone's cart that minimizes the sum of the distances traversed by the drone to pick-up all the items of the CO. We propose algorithms to find such a location when the items to be collected are in Euclidean and Manhattan areas. We can prove a √2-approximation factor for our solutions. Moreover, we compare the efficiency of the automated picking system employing a drone with that of a traditional picking system employing a worker that pushes a cart, and we find under which conditions the drone can be more efficient.

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.

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.

We introduce a drone delivery system for the "last-mile" logistics of small parcels. The system serves mixed delivery areas modeled as EMs. The shortest path between two destinations of an EM concatenates the Euclidean-and Manhattan-distance metrics. The drone's mission consists in one delivery for each destination of the grid, and, due to the strict payload constraint, the drone returns to the warehouse after each delivery. Our goal is to set the drone's warehouse in the delivery area so as the sum of the distances between the locations to be served and the warehouse is minimized. We exactly solve the problem proposing an algorithm that takes logarithmic time in the length of the Euclidean side of the EM. We also devise two approximate solutions that select the warehouse among a constant number of vertices of the EM. Such solutions are almost as good as the exact solution and we prove a √2-approximation bound in the worst case. Finally, we propose an exact solution for the two warehouse problem in a Manhattan grid, and an approximate solution for EMs.