Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30.

Resumo

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)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
• Beneficiário: Rafael Crivellari Saliba Schouery
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos
• Beneficiário: Phablo Fernando Soares Moura
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado