Constant-factor approximations for cycle cover problems

DOI10.1007/978-3-319-44914-2_8MaRDI QIDQ3133203zbMATH OpenOpenAlexFDO

Authors

Publication date 13 February 2018

Published in Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-44914-2_8

zbMATH Keywords

approximation algorithmcycle coverrunning timeundirected graphworst-case analysis

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06)

Recommendations

• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Improved approximation algorithms for min-max and minimum vehicle routing problems
• STACS 2005
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• New approximation algorithms for the minimum cycle cover problem

Cited in

(20)

• Approximation algorithms for maximum latency and partial cycle cover
• An approximation algorithm for the general routing problem
• A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
• An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• Covering tours and cycle covers with turn costs: hardness and approximation
• Star routing: between vehicle routing and vertex cover
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• An optimal strategy for the constrained cycle cover problem
• Improved approximation algorithms for min-max and minimum vehicle routing problems
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Approximation of Euclidean \(k\)-size cycle cover problem
• scientific article; zbMATH DE number 4150221 (Why is no real title available?)
• On Approximating Restricted Cycle Covers
• Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
• A fast (2 + 2/7)-approximation algorithm for capacitated cycle covering
• Practical methods for computing large covering tours and cycle covers with turn cost
• New approximation algorithms for the rooted budgeted cycle cover problem
• New approximation algorithms for the rooted budgeted cycle cover problem
• Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

This page was built for publication: Constant-factor approximations for cycle cover problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133203)