An FPT factor-11 approximation algorithm for TSP

DOI10.1007/978-981-95-0218-9_21MaRDI QIDQ6866524zbMATH OpenFDO

Authors Jianqi Zhou, Zhongyi Zhang, Jiong Guo

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0218-9_21

zbMATH Keywords

fixed-parameter tractablenon-metric graphsparameterized approximationtraveling salesman problem

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A (slightly) improved approximation algorithm for metric TSP
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• A Dynamic Programming Approach to Sequencing Problems
• An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Dynamic Programming Treatment of the Travelling Salesman Problem
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• New inapproximability bounds for TSP
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• P-Complete Approximation Problems
• Parameterized approximation algorithms for TSP
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Performance guarantees for the TSP with a parameterized triangle inequality
• Reducibility among combinatorial problems
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.

This page was built for publication: An FPT factor-11 approximation algorithm for TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866524)