Minimum-weight cycle covers and their approximability
From MaRDI portal
Publication:1028118
DOI10.1016/j.dam.2008.10.005zbMath1172.05344OpenAlexW2095936434MaRDI QIDQ1028118
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
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
