Search

Online social network has deeply changed our lives, such as the style of communication and business, and hence promotes a lot of researches in social influence. The prior works in social influence mainly consider the influence from the view of individuals. However, in many cases, influencing the most of members of an important group such as the board of directors in a company can bring bigger profit than directly influencing the individuals of the company. We call such high profit group which obeys the vote rule as an union, different from existed targeted influence model, we consider such scenarios to make union acceptable and propose the union acceptable profit problem (UAPM) to choose seeds to maximize the union-acceptable profit, i.e., maximize the probability of the union being acceptable. The objective of profit in UAPM is #P-hard, and not submodularity or supmodularity. To solve the problem, we propose an efficient estimation method for the objective and design a heuristic algorithm and further a data-driven β (1 − 1 ϵ) -approximation algorithm where β is the data-driven parameter which is related to the input data. At last we evaluate the performance of the algorithms we proposed on effectiveness and efficiency by the experiments in real-world social network datasets. • We formulate a new problem of UAPM which proved to be hard to solve. • An efficient estimation method for the objective is proposed based on an optimized sampling algorithm. • We propose a heuristic algorithm and a data-driven approximation algorithm respectively to solve the problem. • Experiments with the real-world databases validate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

The problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i.e., average-case) but also the sum of edge weights within the minimum community (i.e., worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition. • A novel objective function of community detection problem is proposed. • The Greedy, Semi-Sandwich Approximation and Local Search algorithms are devised to solve the worst-case problem. • An efficient Terminal-based algorithm is proposed to solve the average-case problem. • An algorithm with the approximate guarantee is proposed for any mixed-case problem. • The experimental results indicate that our proposed methods can form a high-quality community partition. [ABSTRACT FROM AUTHOR]

Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents [1] and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e. , finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP. [ABSTRACT FROM AUTHOR]

This paper considers the laser-charged Unmanned Aerial Vehicle (UAV) assisted Wireless Rechargeable Sensor Network (WRSN), where rechargeable sensors are deployed in surveillance environment to monitor information, a UAV is not only used as aerial wireless mobile collector for gathering data from sensors but also used as mobile charger to replenish energy for sensors, Laser Beam Directors (LBDs) are uniformly deployed in the monitoring environment to charge UAV by emitting laser beams. In such network, we study the average Age of Information Optimization (AoIO) problem whose objective is to minimize the average AoI of data collected from sensors such that all data of the network are transported to the base station and the remaining energy of any sensor exceeds a certain threshold. We prove that the AoIO problem is NP-hard. To solve the AoIO problem, we first study the Total Flight Time Minimizing of UAV (TFTM) problem, which aims at finding an optimal charging solution of UAV to minimize the flight time of UAV based on the order of sensors visited by UAV. Then we prove that the TFTM problem is also NP-hard. Afterwards, we propose a heuristic algorithm to solve the TFTM problem by optimizing flight path, data collection, energy power transfer and laser charging of UAV. Based on the solution for the TFTM problem, we propose an approximation algorithm to solve the AoIO problem. Finally, we conduct extensive simulation experiments to verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on designing and analyzing approximation algorithms with provable approximation guarantees. While these studies revealed interesting effects from a theoretical perspective, so far there has not been a systematic evaluation of the theoretical results in simulations. In this paper, we examine the performance of various approximation algorithms and heuristics for the common scheduling problems on instances generated by different random network models, e.g., taking clustering effects into account. Using (mixed) integer linear programming, we are able to compute the theoretical optima for some of these instances such that the performance of the different algorithms can be compared with these optima. The simulations support the practical relevance of the theoretical findings. For example, setting transmission powers by a square-root power assignment, the network's capacity increases significantly in comparison to uniform power assignments. Furthermore, the developed approximation algorithms are able to exploit this gap providing in general a better performance than any algorithm using uniform transmission powers, even with unlimited computational power. The obtained results are robust against changes in parameters and network generation models. [ABSTRACT FROM AUTHOR]

Abstract: In the minimum common string partition problem one is given two strings S and T with the same character statistics and one seeks for the smallest partition of S into substrings so that T can also be partitioned into the same substring multiset. The problem is fundamental in several variants of edit distance with block operations, e.g. signed reversal distance with duplicates and edit distance with moves. The minimum common string partition problem is known to be NP-complete and the best approximation algorithm known has an approximation factor of . Since the minimum common string partition problem is of utmost practical importance one seeks a heuristic that will (1) usually have a low approximation factor and (2) will run fast. A simple greedy algorithm is known, which iteratively choose non-overlapping longest common substrings of the input strings. This algorithm has been well-studied from an approximation point of view and it has been shown to have a bad worst case approximation factor. However, all the bad approximation factors presented so far stem from complicated recursive construction. In practice the greedy algorithm seems to have small approximation factors. However, the best current implementation of greedy runs in quadratic time. We propose a novel method to implement greedy in linear time. [Copyright &y& Elsevier]

Abstract: All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical–electrical–optical conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP-hard to find a -approximation, where is a positive constant and is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an -approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number of sources running in time. [Copyright &y& Elsevier]

Abstract: Sorting permutations by operations such as reversals and block-moves has received much attention because of its applications in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. In this paper, we investigate the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation, and devise a ()-approximation algorithm for this problem, where is the number of elements divided by the number of inversions in the permutation. The algorithm mostly relies on a new structure in the permutation graph called an umbrella, which can be optimally sorted in time. [Copyright &y& Elsevier]

Abstract: Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power when running at speed , the online heuristic AVR has a competitive ratio . In this paper we first study the online heuristics for the discrete model where the processor can only run at given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio , where is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time and prove that the output schedule is a 3-approximation of the throughput and a -approximation of the energy consumption. [Copyright &y& Elsevier]