Optimal Covering Tours with Turn Costs

DOI10.1137/S0097539703434267zbMath1122.90064OpenAlexW2000889179MaRDI QIDQ5470702

Joseph S. B. Mitchell, Sándor P. Fekete, Esther M. Arkin, Saurabh Sethia, Erik D. Demaine, 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

coveringmanufacturingNP-completenesstraveling salesman problemapproximation algorithmspolynomial-time approximation schememillinglawn mowingNC machiningturn costs\(m\)-guillotine subdivisions

Mathematics Subject Classification ID

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

Related Items (22)

SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ Is It FPT to Cover Points with Tours on Minimum Number of Bends (Errata)? ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ 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 ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Going around in circles ⋮ On the approximability of covering points by lines and related problems ⋮ Unnamed Item ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Improved parameterized algorithms for minimum link-length rectilinear spanning path problem ⋮ The snowblower problem ⋮ FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS ⋮ Traversing a set of points with a minimum number of turns ⋮ DNA origami and the complexity of Eulerian circuits with turning costs ⋮ Milling a Graph with Turn Costs: A Parameterized Complexity Perspective ⋮ On Covering Points with Minimum Turns ⋮ Minimizing the stabbing number of matchings, trees, and triangulations ⋮ Universal hinge patterns for folding strips efficiently into any grid polyhedron ⋮ Minimum Scan Cover with Angular Transition Costs

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