Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/321546
Type: TESE DIGITAL
Title: The geometric connected facility location problem = Problema geométrico conexo de localização de instalações
Title Alternative: Problema geométrico conexo de localização de instalações
Author: Souza, Renata Ghisloti Duarte de, 1987-
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: Resumo: Esse trabalho visa estudar problemas da família Localização de Instalações. Nesses problemas, recebemos de entrada um conjunto de clientes e um conjunto de instalações. Queremos encontrar e abrir um subconjunto de instalações, normalmente, pagando um preço por cada instalação aberta. Nosso objetivo é conectar clientes a instalações abertas, pagando o menor custo possível. Esse problema tem grandes aplicações na área de Pesquisa Operacional e Telecomunicações. Estamos especialmente interessados no problema de Localização de Instalações Geométrico e Conexo. Nessa versão do problema, as instalações podem ser abertas em qualquer lugar de um plano de dimensão d, e pagamos um preço fixo f por cada instalação aberta. Também devemos conectar as instalações entre si formando uma árvore. Essa árvore normalmente recebe uma ponderação maior, uma vez que suas conexões agregam atendimento para quantidade maior de recursos. Para representar tal ponderação seus custos são multiplicados por um parametro M > 0 dado como parte da entrada. Apresentamos um Esquema de Aproximação Polinomial para a versão euclidiana do problema

Abstract: In this work we study problems from the facility location family. In this set of problems, we want to find and open a subset of given facilities. Usually, a price is paid for each opened facility. Our goal is to connect given clients to the closest opened facilities incurring in the smallest cost possible. This problem has several practical applications in Operations Research and Telecommunication. We are specially interested in the Geometric Connected Facility Location problem. In this version, facilities can be anywhere in the d-dimensional plane, and we have to pay a fixed price f to open each facility. We also have the requirement of connecting facilities among themselves forming a tree. This tree is usually weighted by a given parameter M > 0. We present a Polynomial-Time Approximation Scheme for the two-dimensional version of this problem
Subject: Algoritmos de aproximação
Teoria da computação
Language: Inglês
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Souza_RenataGhislotiDuartede_M.pdf773.71 kBAdobe PDFView/Open


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