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

A PTAS for the Geometric Connected Facility Location Problem

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 type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 13/21744-8 - Theoretical and Pratical Approaches to Packing Problems
Grantee:Rafael Crivellari Saliba Schouery
Support type: Scholarships in Brazil - Post-Doctorate