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

DOI10.1007/978-3-030-17402-6_19MaRDI QIDQ2294052zbMATH OpenOpenAlexFDO

Authors Sándor P. Fekete, Dominik Krupke

Publication date 6 February 2020

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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

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)