Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication

DOI10.1145/3357713.3384264MaRDI QIDQ5144895zbMATH OpenOpenAlexFDO

Authors Jesper Nederlof

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384264

zbMATH Keywords

exponential time algorithmstraveling salesman problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Polynomially solvable cases of the bipartite traveling salesman problem
• Probabilistic analysis of bipartite traveling salesman problems
• New approximation algorithms for \((1,2)\)-TSP
• Approximation algorithms for the Euclidean bipartite TSP
• Approximating the bipartite TSP and its biased generalization

Cited in

(4)

• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
• Determinantal sieving

This page was built for publication: Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication

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