A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph

DOI10.1134/S0081543815050107zbMath1409.05158MaRDI QIDQ492282

Mikhail Yu. Khachay, Katherine Neznakhina

Publication date: 20 August 2015

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

zbMATH Keywords

traveling salesman problemNP-hard problempolynomial-time approximation schemecycle cover of size \(k\)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (6)

Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ An exact algorithm with linear complexity for a problem of visiting megalopolises ⋮ Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles ⋮ A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• The vehicle routing problem. Latest advances and new challenges.
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• The Euclidean traveling salesman problem is NP-complete
• Quad trees: A data structure for retrieval by composite keys
• The Truck Dispatching Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• P-Complete Approximation Problems
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph