Search

Travelling salesman problem (TSP) is a graph problem that has been widely used in many applications, especially for transportation and logistics. Because TSP is a NP hard problem, minimizing the complexity of TSP algorithms is an important problem. Many heuristic algorithms have been proposed to compute the TSP tours of a given static graph. But limited studies have been done on time-evolving graph (TEG) where the graph can change over time due to update events, such as weight changes on edges or vertices. It is a more challenging problem because the speed of TSP computations must be high enough to catch up the graph update frequency. In this paper, we make the very first attempt to minimize the computation time of solving TSP on time-evolving graphs. By exploring parallel computing power and reusing previous computing results, we proposed a distributed and incremental TSP algorithm which can be implemented on vertex-centric parallel graph computing frameworks to efficiently find TSP tours on large changing graphs. Our incremental algorithm can maintain shortest TSP tour with minimum amount of recomputation. Through our experimental evaluation, we have shown incremental TSP algorithm is 98% faster than distributed algorithm. [ABSTRACT FROM AUTHOR]

Server virtualization and consolidation techniques have been widely adapted in the modern large-scale computing systems to reduce energy consumption and increase resource utilization. In these systems, physical servers are turned on/off dynamically according to the workload variation, and the loading from computing tasks are balanced among active servers through virtual machine (VM) migration. However, the downside of this approach is the overhead of VM migration can cause several negative impacts to the system and users, including application performance degradation, service interruption, prolonged job execution time, extra network bandwidth consumption, and risk of failure, etc. The existing works in the literature attempt to reduce VM migration cost for persistent running web servers in a reactive manner. In contrast, we tackle the problem for parallel computing jobs of batch processing systems. Our approach can proactively avoid VM migrations with the co-design of between job scheduling and VM consolidation strategies, and minimize communication overhead of jobs by considering the traffic pattern between the tasks of a job. Our evaluations have used real parallel job workload trace and a synthetically generated workload to show that our approach can notably reduce the number of VM migrations by 35%–50% and communication cost by up to 25% compared to the traditional job scheduling approaches. [ABSTRACT FROM AUTHOR]