Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane

Full text
Author(s):
Lintzmayer, Carla N. [1] ; Miyazawa, Flavio K. [2] ; Moura, Phablo F. S. [2] ; Xavier, Eduardo C. [2]
Total Authors: 4
Affiliation:
[1] Fed Univ ABC, Ctr Math Comp & Cognit, Santo Andre, SP - Brazil
[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Total Affiliations: 2
Document type: Journal article
Source: THEORETICAL COMPUTER SCIENCE; v. 835, p. 134-155, OCT 2 2020.
Web of Science Citations: 0
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 ofnpairs of points (terminals) T = [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. (c) 2020 Elsevier B.V. All rights reserved. (AU)

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/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
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: 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: 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