Randomized approximation scheme for Steiner multi cycle in the Euclidean plane

DOI10.1016/J.TCS.2020.06.022MaRDI QIDQ2192387zbMATH OpenOpenAlexWikidataFDO

Authors Carla Negri Lintzmayer, Flávio K. Miyazawa, Phablo F. S. Moura, Eduardo C. Xavier

Publication date 17 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.06.022

zbMATH Keywords

approximation algorithmEuclidean planerandomized algorithmSteiner multi-cycle

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Recommendations

• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• scientific article; zbMATH DE number 1670876
• scientific article; zbMATH DE number 1163704
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph

Cites work

• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing
• Approximability of the minimum Steiner cycle problem
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Approximation schemes for Euclidean vehicle routing problems with time windows
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Shipper collaboration
• The Steiner cycle polytope

Cited in

(6)

• Quasilinear approximation scheme for Steiner multi cycle in the Euclidean plane
• A Dual-Radix Approach to Steiner’s 1-Cycle Theorem
• Approximations for the Steiner multicycle problem
• Approximations for the Steiner multicycle problem
• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
• On the restricted Steiner multi cycle problem

This page was built for publication: Randomized approximation scheme for Steiner multi cycle in the Euclidean plane

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