A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP

A. N. Glebov, S. G. Toktokhoeva

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We present a first polynomial algorithm with guaranteed approximation ratio for the asymmetric maximization version of the asymmetric 3-Peripatetic Salesman Problem (3-APSP). This problem consists in finding the three edge-disjoint Hamiltonian circuits of maximal total weight in a complete weighted digraph. We prove that the algorithm has guaranteed approximation ratio 3/5 and cubic running-time.

Original languageEnglish
Pages (from-to)219-238
Number of pages20
JournalJournal of Applied and Industrial Mathematics
Volume13
Issue number2
DOIs
Publication statusPublished - 1 Apr 2019

Keywords

  • approximation algorithm
  • guaranteed approximation ratio
  • Hamiltonian cycle
  • m-peripatetic salesman problem
  • traveling salesman problem

Fingerprint Dive into the research topics of 'A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP'. Together they form a unique fingerprint.

Cite this