Please use this identifier to cite or link to this item:

`http://repositorio.unicamp.br/jspui/handle/REPOSIP/329853`

Type: | Artigo |

Title: | Clustering Through Continuous Facility Location Problems Clustering through continuous facility location problems |

Author: | Meira, Luis A. A. Miyazawa, Flavio K. Pedrosa, Lehilton L. C. |

Abstract: | We consider the Continuous Facility Location Problem (ConFLP). Given a finite set of clients C subset of R-d and a number f is an element of R+, ConFLP consists in opening a set F' subset of R-d of facilities, each at cost f, and connecting each client to an open facility. The objective is to minimize the costs of opening facilities and connecting clients. We reduce ConFLP to the standard Facility Location Problem (FLP), by using the so-called approximate center sets. This reduction preserves the approximation, except for an error epsilon, and implies 1.488 + epsilon and 2.04 + epsilon-approximations when the connection cost is given by the Euclidean distance and the squared Euclidean distance, respectively. Moreover, we obtain approximate center sets for the case that the connection cost is the ath power of the Euclidean distance, achieving approximations for the corresponding problems, for any alpha >= 1. As a byproduct, we also obtain a polynomial-time approximation scheme for the k-median problem with this cost function, for any fixed k. (C) 2016 Elsevier B.V. All rights reserved. We consider the Continuous Facility Location Problem (ConFLP). Given a finite set of clients C subset of R-d and a number f is an element of R+, ConFLP consists in opening a set F' subset of R-d of facilities, each at cost f, and connecting each client to |

Subject: | Continuous Facility Location Problem K-clustering Approximate Center Sets Random Sampling Procedure Approximation Algorithms Algoritmos de aproximação Otimização combinatória Localização de instalações (Pesquisa operacional) |

Country: | Países Baixos |

Editor: | Elsevier |

Citation: | Theoretical Computer Science . Elsevier Science Bv, v. 657, p. 137 - 145, 2017. |

Rights: | fechado fechado |

Identifier DOI: | 10.1016/j.tcs.2016.10.001 |

Address: | https://www.sciencedirect.com/science/article/pii/S030439751630514X |

Date Issue: | 2017 |

Appears in Collections: | IC - Artigos e Outros Documentos FT - Artigos e Outros Documentos |

Files in This Item:

File | Size | Format | |
---|---|---|---|

000390971500003.pdf | 435.58 kB | Adobe PDF | View/Open |

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.