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

A. N. Glebov, S. G. Toktokhoeva

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)219-238
Число страниц20
ЖурналJournal of Applied and Industrial Mathematics
Том13
Номер выпуска2
DOI
СостояниеОпубликовано - 1 апр 2019

Fingerprint Подробные сведения о темах исследования «A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать