Fat computational complexity and heuristic design for the TSP

DOI10.3724/SP.J.1001.2009.03418MaRDI QIDQ3054243zbMATH OpenOpenAlexFDO

Authors He Jiang, Yan Hu, Qiang Li, Hong Yu

Publication date 5 November 2010

Published in Journal of Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3724/sp.j.1001.2009.03418

zbMATH Keywords

heuristic algorithmNP-hardtraveling salesman problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Worst-case analysis of a new heuristic for the travelling salesman problem
• The parallel complexity of TSP heuristics
• scientific article; zbMATH DE number 795217
• The traveling salesman problem and its variations
• TSP heuristics: domination analysis and complexity

Cited in

(3)

• The parallel complexity of TSP heuristics
• Fine-grained Complexity Analysis of Two Classic TSP Variants
• scientific article; zbMATH DE number 2243051 (Why is no real title available?)

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Fat computational complexity and heuristic design for the TSP

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