Search

In social networks, the minimum positive influence dominating set (MPIDS) problem is NP-hard, which means it is unlikely to be solved precisely in polynomial time. For the purpose of efficiently solving this problem, greedy approximation algorithms seem appealing because they are fast and can provide guaranteed solutions. In this paper, based on the classic greedy algorithm for cardinality submodular cover, we propose a general greedy approximation algorithm (GGAA) for the MPIDS problem, which uses a generic real-valued submodular potential function, and enjoys a provable approximation guarantee under a wide condition. Two existing greedy algorithms, one of which is unknown for having an approximation ratio, both can be viewed as the specific versions of GGAA, and are shown to enjoy an approximation guarantee of the same order. Applying the framework of GGAA, we also design two new greedy approximation algorithms with fractional submodular potential functions. All these greedy algorithms are $$O(\ln \alpha )$$ -approximations where $$\alpha $$ is the maximum node degree of the network graph, while it is shown experimentally that these two new algorithms can yield better solutions on typical real social network instances. In this work, as a by-product, we achieve a new approximation ratio of the classic greedy algorithm for cardinality submodular cover, which slightly generalizes two existing results.

With the explosive growth in the scale of cloud computing infrastructures, reliability and energy efficiency have become important concerns considering the great complexity of cloud data centers. There is an urgent need for efficient task assignment that can dispatch tasks to appropriate cloud data center servers, which is critical to achieve reliability and energy efficiency in current cloud data centers. Most of the research on task assignment focuses on only one of the objectives of reliability and energy efficiency, while the two objectives are intrinsically conflicting with each other. In this paper, we deal with the problem of task assignment in data centers, with the objective of minimizing the energy consumption while providing failure tolerance to task execution failure. We propose a reliability-aware and energy-efficient task replica assignment algorithm based on running task replicas at a low speed and enabling multiple task replicas to share the same server resources. Each task in a job processed by the cloud computing platform has two instances: main task and task replica (shadow). Each main task runs on an individual server, and the task replica associated with the main task is assigned on a different server. The main tasks run at the full server speed, while the task replicas run at a lower rate than the main tasks. The task replicas can be mapped onto dedicated backup servers or be assigned to the servers on which the main tasks are running. Multiple task replicas can share the same server resources to reduce the number of servers required. We conduct experiments through simulations. Experimental results demonstrate that the proposed algorithm can effectively reduce the energy consumption, while achieving a good balance between the number of servers used and job completion time.