Minimum-weight cycle covers and their approximability

DOI10.1016/j.dam.2008.10.005zbMath1172.05344MaRDI QIDQ1028118

Bodo Manthey

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/minimumweight-cycle-covers-and-their-approximability(b9c53f78-fcd3-445c-8769-0d95f9e6907f).html

zbMATH Keywords

approximation algorithms; inapproximability; cycle covers; non-constructive algorithms

Mathematics Subject Classification ID

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight, Approximability of the minimum-weight \(k\)-size cycle cover problem, Relaxations of Combinatorial Problems Via Association Schemes, Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the TSP with sharpened triangle inequality
• Erratum to ``An approximation algorithm for maximum triangle packing
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem
• Improved deterministic approximation algorithms for max TSP
• An extension of matching theory
• Matching theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the complexity of the \(k\)-customer vehicle routing problem
• Improved approximation algorithms for metric MaxTSP
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• On Approximating Restricted Cycle Covers
• Nonconstructive tools for proving polynomial-time decidability
• On Restricted Two-Factors
• P-Complete Approximation Problems
• Linear approximation of shortest superstrings
• A General Approximation Technique for Constrained Forest Problems
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Data Structures