A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension

DOI10.1134/S0081543816090133zbMath1369.90147MaRDI QIDQ2396378

Katherine Neznakhina

Publication date: 8 June 2017

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

zbMATH Keywords

traveling salesman problemNP-hard problemcycle cover of size \(k\)polynomialtime approximation scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Approximability of the problem about a minimum-weight cycle cover of a graph
• The Euclidean traveling salesman problem is NP-complete
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximation of Euclidean k-size cycle cover problem
• P-Complete Approximation Problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Reducibility among Combinatorial Problems