Approximability of the minimum-weight k-size cycle cover problem
DOI10.1007/S10898-015-0391-3zbMATH Open1355.90084OpenAlexW2461269952MaRDI QIDQ330503FDOQ330503
Authors: Katherine Neznakhina, M. Yu. Khachaĭ 
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
Recommendations
- Approximation of Euclidean \(k\)-size cycle cover problem
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
- Constant-factor approximations for cycle cover problems
- Improved approximation algorithms for min-max and minimum vehicle routing problems
NP-hard problemcycle cover problem (CCP)polynomial-time approximation scheme (PTAS)traveling salesman problem (TSP)
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- Introduction to algorithms
- Title not available (Why is that?)
- 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
- The vehicle routing problem. Latest advances and new challenges.
- The Euclidean traveling salesman problem is NP-complete
- P-Complete Approximation Problems
- Minimum-weight cycle covers and their approximability
- Approximating maximum weight cycle covers in directed graphs with weights zero and one
- Title not available (Why is that?)
- Lower bounds for symmetricK-peripatetic salesman problems
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
- Title not available (Why is that?)
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
- On Approximating Restricted Cycle Covers
- Title not available (Why is that?)
- An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
- On the relationship between ATSP and the cycle cover problem
Cited In (11)
- An overview of graph covering and partitioning
- New approximation algorithms for the rooted budgeted cycle cover problem
- Approximating the Minimum Tour Cover with a Compact Linear Program
- 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
- New approximation algorithms for the rooted budgeted cycle cover problem
- Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
- Approximating maximum weight cycle covers in directed graphs with weights zero and one
- Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
- Approximation algorithms for some minimum postmen cover problems
- Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
Uses Software
This page was built for publication: Approximability of the minimum-weight \(k\)-size cycle cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q330503)
