Approximability of the minimum-weight \(k\)-size cycle cover problem

DOI10.1007/s10898-015-0391-3zbMath1355.90084OpenAlexW2461269952MaRDI QIDQ330503

Katherine Neznakhina, Mikhail Yu. Khachay

Publication date: 26 October 2016

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-015-0391-3

zbMATH Keywords

traveling salesman problem (TSP)NP-hard problemcycle cover problem (CCP)polynomial-time approximation scheme (PTAS)

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (9)

An overview of graph covering and partitioning ⋮ Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces ⋮ Randomized approximation scheme for Steiner multi cycle in the Euclidean plane ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ New approximation algorithms for the rooted budgeted cycle cover problem

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem
• The vehicle routing problem. Latest advances and new challenges.
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• Minimum-weight cycle covers and their approximability
• The Euclidean traveling salesman problem is NP-complete
• Quad trees: A data structure for retrieval by composite keys
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• The Truck Dispatching Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On Approximating Restricted Cycle Covers
• P-Complete Approximation Problems
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: Approximability of the minimum-weight \(k\)-size cycle cover problem