Optimal Covering Tours with Turn Costs

DOI10.1137/S0097539703434267MaRDI QIDQ5470702zbMATH OpenOpenAlexFDO

Authors Esther M. Arkin, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia, Michael A. Bender

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539703434267

zbMATH Keywords

\(m\)-guillotine subdivisionsapproximation algorithmscoveringlawn mowingmanufacturingmillingNC machiningNP-completenesspolynomial-time approximation schemetraveling salesman problemturn costs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Optimal covering tours with turn costs
• Approximation algorithms for lawn mowing and milling
• On Covering Points with Minimum Turns
• Practical methods for computing large covering tours and cycle covers with turn cost
• Approximation algorithms for the Geometric Covering Salesman Problem

Cited in

(35)

• Minimizing the stabbing number of matchings, trees, and triangulations
• The traveling salesman problem on grids with forbidden neighborhoods
• Approximation algorithms for lawn mowing and milling
• DNA origami and the complexity of Eulerian circuits with turning costs
• Covering tours and cycle covers with turn costs: hardness and approximation
• Optimal covering tours with turn costs
• An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
• Is it FPT to cover points with tours on minimum number of bends (errata)?
• FPT-algorithms for minimum-bends tours
• Experimental evaluation of algorithms for the orthogonal milling problem with turn costs
• Milling a graph with turn costs: a parameterized complexity perspective
• Minimum covering with travel cost
• Going around in circles
• scientific article; zbMATH DE number 1555918 (Why is no real title available?)
• APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• Minimum scan cover with angular transition costs
• SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
• SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition
• Practical methods for computing large covering tours and cycle covers with turn cost
• On Covering Points with Minimum Turns
• The snowblower problem
• Traversing a set of points with a minimum number of turns
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs
• Edge sparsification for geometric tour problems
• Grid recognition: classical and parameterized computational perspectives
• A closer cut: computing near-optimal lawn mowing tours
• What goes around comes around: covering tours and cycle covers with turn costs
• The Hamiltonian path graph is connected for simple s,t paths in rectangular grid graphs
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization
• Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
• Sweeping a domain with line-of-sight between covisible agents
• On the approximability of covering points by lines and related problems
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity

This page was built for publication: Optimal Covering Tours with Turn Costs

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