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.)

A PTAS for the Geometric Connected Facility Location Problem

Texto completo
Autor(es):
Miyazawa, Flavio K. ; Pedrosa, Lehilton L. C. ; Schouery, Rafael C. S. ; de Souza, Renata G. D.
Número total de Autores: 4
Tipo de documento: Artigo Científico
Fonte: THEORY OF COMPUTING SYSTEMS; v. 61, n. 3, p. 871-892, OCT 2017.
Citações Web of Science: 0
Resumo

We consider the Geometric Connected Facility Location Problem (GCFLP): given a set of clients , one wants to select a set of locations where to open facilities, each at a fixed cost fa0. For each client , one has to choose to either connect it to an open facility I center dot(j)aF paying the Euclidean distance between j and I center dot(j), or pay a given penalty cost pi(j). The facilities must also be connected by a tree T, whose cost is M a{''}{''}(T), where Mae1 and a{''}{''}(T) is the total Euclidean length of edges in T. The multiplication by M reflects the fact that interconnecting two facilities is typically more expensive than connecting a client to a facility. The objective is to find a solution with minimum cost. In this paper, we present a Polynomial-Time Approximation Scheme (PTAS) for the two-dimensional GCFLP. Our algorithm also leads to a PTAS for the two-dimensional Geometric Connected k-medians, when f=0, but only k facilities may be opened. (AU)

Processo FAPESP: 14/14209-1 - Algoritmos de aproximação para problemas de projeto de rede com restrições
Beneficiário:Lehilton Lelis Chaves Pedrosa
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/21744-8 - Abordagens teóricas e práticas para problemas de empacotamento
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Bolsas no Brasil - Pós-Doutorado