Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane

Texto completo
Autor(es):
Lintzmayer, Carla N. [1] ; Miyazawa, Flavio K. [2] ; Moura, Phablo F. S. [2] ; Xavier, Eduardo C. [2]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Fed Univ ABC, Ctr Math Comp & Cognit, Santo Andre, SP - Brazil
[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: THEORETICAL COMPUTER SCIENCE; v. 835, p. 134-155, OCT 2 2020.
Citações Web of Science: 0
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 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)

Processo FAPESP: 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
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
Linha de fomento: Auxílio à Pesquisa - Temático
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
Linha de fomento: Auxílio à Pesquisa - Temático