Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane

Author(s)

Lintzmayer, Carla N. ; Miyazawa, Flavio K. ; Moura, Phablo F. S. ; Xavier, Eduardo C.

• Document type: Journal article
• Source: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30.

Abstract

We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set of n pairs of points (terminals) tau = {{t(i), t(i)'}(i=1)(n) in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that t(i) and t(i)' belong to a same cycle, for each i is an element of {1, ... , n}. This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations. (AU)

• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 17/22611-2 - Algorithmic and structural aspects of covering and packing problems on graphs
• Grantee: Phablo Fernando Soares Moura
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• FAPESP's process: 16/23552-7 - Cutting and Packing Problems: Practical and Theoretical Approaches
• Grantee: Rafael Crivellari Saliba Schouery
• Support Opportunities: Regular Research Grants
• FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 16/21250-3 - Algorithmic and structural aspects of Covering and Packing problems on graphs
• Grantee: Phablo Fernando Soares Moura
• Support Opportunities: Scholarships in Brazil - Post-Doctoral