Improved Approximation Algorithms for Metric Max TSP | Zendy

ZhiZhong Chen | Zendy; Takayuki Nagoya | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Improved Approximation Algorithms for Metric Max TSP

Author(s) -

ZhiZhong Chen,

Takayuki Nagoya

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-29118-0

DOI - 10.1007/11561071_18

Subject(s) - travelling salesman problem , approximation algorithm , metric (unit) , combinatorics , computer science , undirected graph , discrete mathematics , algorithm , mathematics , graph , operations management , economics

We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is $\frac{27}{35}$. The other is for undirected graphs and its approximation ratio is $\frac{7}{8} - o(1)$. Both algorithms improve on the previous bests.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research