A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
From MaRDI portal
(Redirected from Publication:492282)
traveling salesman problempolynomial-time approximation schemeNP-hard problemcycle cover of size \(k\)
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Approximation of Euclidean \(k\)-size cycle cover problem
- Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
- An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
- A polynomial-time approximation scheme for embedding hypergraph in a cycle
- Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
- On approximating maximum covering cycles in undirected graphs
- A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph
- On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
- scientific article; zbMATH DE number 1223730
- On Approximating Restricted Cycle Covers
Cites work
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3485514 (Why is no real title available?)
- scientific article; zbMATH DE number 3625145 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- Lower bounds for symmetricK-peripatetic salesman problems
- On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
- P-Complete Approximation Problems
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Quad trees: A data structure for retrieval by composite keys
- The Euclidean traveling salesman problem is NP-complete
- The truck dispatching problem
- The vehicle routing problem. Latest advances and new challenges.
Cited in
(12)- The Euclidean distance completion problem: cycle completability
- A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
- An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
- Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
- 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
- Approximability of the minimum-weight \(k\)-size cycle cover problem
- Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
- On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
- Approximation of Euclidean \(k\)-size cycle cover problem
- Approximation algorithms for multi-robot patrol-scheduling with min-max latency
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
This page was built for publication: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492282)
