Covering tours and cycle covers with turn costs: hardness and approximation

DOI10.1007/978-3-030-17402-6_19OpenAlexW2887688500MaRDI QIDQ2294052FDOQ2294052

Authors: Sándor P. Fekete, Dominik Krupke 

Publication date: 6 February 2020

Full work available at URL: https://arxiv.org/abs/1808.04417

Recommendations

• Practical methods for computing large covering tours and cycle covers with turn cost
• Optimal covering tours with turn costs
• Optimal Covering Tours with Turn Costs
• Constant-factor approximations for cycle cover problems
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximating the Minimum Tour Cover with a Compact Linear Program
• On Approximating Restricted Cycle Covers
• Approximation and Online Algorithms
• On approximating maximum covering cycles in undirected graphs
• Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (5)

• SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
• Approximating the Minimum Tour Cover with a Compact Linear Program
• What goes around comes around: covering tours and cycle covers with turn costs
• Minimum scan cover with angular transition costs
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization

This page was built for publication: Covering tours and cycle covers with turn costs: hardness and approximation

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