We present a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan which is designed and optimized for running efficiently on the GPU. The algorithm is a Polynomial Time Approximation Scheme (PTAS) based on a higher-dimensional dynamic programming approach, where dimensionality refers to the number of variables in the dynamic programming equation characterizing the problem. The main component of our design consists of a novel data-partitioning technique that is employed to accelerate the higher-dimensional dynamic programming component of the algorithm. We present performance results to demonstrate how our proposed design improves the GPU utilization and makes it possible to solve large higher-dimensional dynamic programming problems with the limited GPU memory. Experimental results show that the GPU implementation outperforms the optimized OpenMP implementation of the approximation algorithm.
Complex networks can explain the relationship between the nodes or the systems in the real world, and their topology determines the influence of nodes in network. Among them, the identification of influence nodes has become an important research content in complex networks because of its influence in different fields. It has played an important role that cannot be ignored in the construction of emergency logistics networks, social network, transportation network, biological virus network and power network. In the real social network, the key figures or important information in the network can effectively control the information transmission in the network and carry out marketing activities. Therefore, aiming at the common problems of existing algorithms, including the inaccurate results of simple methods and the high computational complexity of precise methods combined with actual properties in the network, this paper will deeply study the optimization problems affecting node identification in complex networks based on voting method, and proposed a voting method for key node identification based on multi-attributes (VMM) in social networks, such as degree value, clustering coefficient and number of neighbors of nodes are integrated into the voting process. By comparing the classical algorithms and the voting algorithms under the SIR model, VMM algorithms can effectively identify the key nodes in the social network.