Minimum-weight cycle covers and their approximability

DOI10.1016/j.dam.2008.10.005zbMath1172.05344OpenAlexW2095936434MaRDI 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 algorithmsinapproximabilitycycle coversnon-constructive algorithms

Mathematics Subject Classification ID

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

Related Items (5)

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 ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles ⋮ Relaxations of Combinatorial Problems Via Association Schemes

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

This page was built for publication: Minimum-weight cycle covers and their approximability