| Title: |
Approximation Algorithm for Travelling Salesman Problem |
| Authors: |
Oladele, R. O; Mobolaji, D. M. |
| Source: |
University of Ibadan Journal of Science and Logics in ICT Research; Vol. 14 No. 1 (2025): Journal of Science and Logics in ICT Research |
| Publisher Information: |
University of Ibadan Journal of Science and Logics in ICT Research |
| Publication Year: |
2025 |
| Collection: |
University of Ibadan Journal System |
| Subject Terms: |
Hamiltonian ath; Linear Programming; Relaxation; Semi-Definite Programming |
| Description: |
Designing approximation algorithms often involves, among other things, relaxing the integrality constraint and obtaining a convex relaxation of the problem. The most well-known relaxation schemes are the Linear Programming (LP) relaxation and Semi-Definite Programing (SDP) relaxation. While LP relaxation has been widely used for solving TSP, SDP has been rarely employed. The primary goal of this paper therefore is to employ SDP and develop approximation algorithm for metric TSP. The SDP relaxation of the TSP is first obtained, and the approximation algorithm is thereafter developed. When compared to optimal results of some standard TSP instances, implementation result showed a relatively fair performance. |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
https://journals.ui.edu.ng/index.php/uijslictr/article/view/2022/1584; https://journals.ui.edu.ng/index.php/uijslictr/article/view/2022 |
| Availability: |
https://journals.ui.edu.ng/index.php/uijslictr/article/view/2022 |
| Rights: |
Copyright (c) 2025 University of Ibadan Journal of Science and Logics in ICT Research |
| Accession Number: |
edsbas.5F62B7D0 |
| Database: |
BASE |