| Full text | |
| Author(s): |
Miyazawa, Flavio K.
;
Pedrosa, Lehilton L. C.
;
Schouery, Rafael C. S.
;
de Souza, Renata G. D.
Total Authors: 4
|
| Document type: | Journal article |
| Source: | THEORY OF COMPUTING SYSTEMS; v. 61, n. 3, p. 871-892, OCT 2017. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 14/14209-1 - Approximation algorithms for network design problems with restrictions |
| Grantee: | Lehilton Lelis Chaves Pedrosa |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/21744-8 - Theoretical and Pratical Approaches to Packing Problems |
| Grantee: | Rafael Crivellari Saliba Schouery |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |