1,720,973 research outputs found
On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
No full textIn the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph G = (V,E) and an integer B and we are asked to find B new edges to be added to G in order to maximize the number of connected pairs of vertices in the resulting graph. The MCI problem has been studied from the approximation point of view. In this paper, we approach it from the parameterized complexity perspective in the case of directed acyclic graphs. We show several hardness and algorithmic results with respect to different natural parameters. Our main result is that the problem is W[2]-hard for parameter B and it is FPT for parameters |V |- B and nu, the matching number of G. We further characterize the MCI problem with respect to other complementary parameters
On the Maximum Connectivity Improvement Problem
No full textIn this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph a weight function (formula presented), a profit function (formula presented), and an integer B, find a set S of at most B edges not in E that maximises (formula presented), where p(R(v, S)) is the sum of the profits of the nodes reachable from node v when the edges in S are added to G. We first show that we can focus on Directed Acyclic Graphs (DAG) without loss of generality. We prove that the MCI problem on DAG is NP-Hard to approximate to within a factor greater than 1-1/e even if we restrict to graphs with a single source or a single sink, and MCI remains NP -Complete if we further restrict to unitary weights. We devise a polynomial time algorithm based on dynamic programming to solve the MCI problem on trees with a single source. We propose a polynomial time greedy algorithm that guarantees (1-1/e) -approximation ratio on DAGs with a single source or a single sink
Border effects on connectivity for randomly oriented directional antenna networks
No full textWe study the possibility of creating a fully con-nected ad-hoc network with bidirectional links between nodes equipped with randomly oriented directional antennas de-ployed in a circular planar region. The major contribution of our paper is to show that in the directional antenna setting there are always isolated nodes, no matter how high the transmission power of the antennas. We observe, however, that the isolated nodes are confined to a narrow annulus near the boundary of the region. We propose two solutions to achieve full connectivity in the directional setting: T-core that reorients isolated antennas towards the centre of the circular region, and Greedy that simply flips the antenna orientation. We show that the former heuristic, which needs information of the location of the centre of the region, achieves full connectivity with high probability and that, even the latter, which requires no extra information, is able to eliminate most of the isolation
Automated picking system employing a drone
No full textWe 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
Election Control Through Social Influence with Unknown Preferences
No full textThe election control problem through social influence asks to find a set of nodes in a social network of voters to be the starters of a political campaign aiming at supporting a given target candidate. Voters reached by the campaign change their opinions on the candidates. The goal is to shape the diffusion of the campaign in such a way that the chances of victory of the target candidate are maximized. Previous work shows that the problem can be approximated within a constant factor in several models of information diffusion and voting systems, assuming that the controller, i.e., the external agent that starts the campaign, has full knowledge of the preferences of voters. However this information is not always available since some voters might not reveal it. Herein we relax this assumption by considering that each voter is associated with a probability distribution over the candidates. We propose two models in which, when an electoral campaign reaches a voter, this latter modifies its probability distribution according to the amount of influence it received from its neighbors in the network. We then study the election control problem through social influence on the new models: In the first model, under the Gap-ETH, election control cannot be approximated within a factor better than, where n is the number of voters; in the second model, which is a slight relaxation of the first one, the problem admits a constant factor approximation algorithm
Balancing spreads of influence in a social network
No full textThe 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
Robust Federated Learning against Backdoor Attackers
No full textFederated learning is a privacy-preserving alter-native for distributed learning with no involvement of data transfer. As the server does not have any control on clients' actions, some adversaries may participate in learning to introduce corruption into the underlying model. Backdoor attacker is one such adversary who injects a trigger pattern into the data to manipulate the model outcomes on a specific sub-task. This work aims to identify backdoor attackers and to mitigate their effects by isolating their weight updates. Leveraging the correlation between clients' gradients, we propose two graph theoretic algorithms to separate out attackers from the benign clients. Under a classification task, the experimental results show that our algorithms are effective and robust to the attackers who add backdoor trigger patterns at different location in targeted images. The results also evident that our algorithms are superior than existing methods especially when numbers of attackers are more than the normal clients
JTeC: A Large Collection of Java Test Classes for Test Code Analysis and Processing
Full text linkThe 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
Recommending Links to Maximize the Influence in Social Networks
No full textSocial 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
- …
