Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Indonesian Journal of Electrical Engineering and Computer Science
Arya, Akschat
Unknown Affiliation

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Parallelized solution to the asymmetric travelling salesman problem using central processing unit acceleration Arya, Akschat; Perumal, Boominathan; Krishnan, Santhi
Indonesian Journal of Electrical Engineering and Computer Science Vol 25, No 3: March 2022
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.11591/ijeecs.v25.i3.pp1795-1802

Abstract

Travelling salesman problem is a well researched problem in computer science and has many practical applications. It is classified as a NP-hard problem as its exact solution can only be obtained in exponential time unless P = NP. There are different variants of the travelling salesman problem (TSP) and in this paper, asymmetric travelling salesman problem is addressed since this variant is quite often observed in real world scenarios. There are a number of heuristic approaches to this problem which provides approximate solutions in polynomial time, however this paper proposes an exact optimal solution which is accelerated with the help of multi-threading-based parallelization. In order to find the exact optimal solution, we have used the held-karp algorithm involving dynamic programming and to reduce the time taken to find the optimal path, we have used a multi-threaded approach to parallelize the processing of sub-problems by leveraging the central processing unit cores (CPUs). This method is an extension of a well researched solution to the TSP; however, this method shows that solutions to computationally intensive problems involving sub-problems such as the asymmetic travelling salesman problem (ATSP) can be accelerated with the help of modern CPUs.
Co-Authors Krishnan, Santhi Perumal, Boominathan