Resumo: Neste trabalho estudamos a interação entre duas áreas: otimização combinatória e compartilhamento de custos (cost-sharing), que é a arte de dividir os custos associados a construção e manutenção de uma solução a qual um grupo de usuários é beneficiado. Apresentamos algoritmos para problemas de projeto de redes, tendo como objetivo principal os problemas ¿Connected Facility Location¿ e ¿Rent-or-Buy¿. Estes dois problemas são NP-difíceis, pois têm como caso particular o problema da arvore mínima de Steiner, que tambem é NP-dificil. Na primeira parte do trabalho, temos a seguinte questão como motivação: ¿Como projetar uma boa rede, ou seja, uma rede que satisfaça todas as propriedades do problema e ao mesmo tempo minimize o custo de construção desta rede?¿ 'E nesta parte que os algoritmos de aproximação entram em ação. Uma vez que esse custo for determinado, na segunda parte do trabalho, uma outra questão surge: ¿Como dividir esse custo entre todos os usuários que participam da rede de uma maneira ¿justa¿? Nesta parte, usaremos o compartilhamento de custos juntamente com as tecnicas de algoritmos de aproximação para responder a essa questão Ver menos

Abstract: We consider the interplay of two areas: combinatorial optimization and cost-sharing in network design problems. In the first, we are interested to find a solution with small cost. In the second we would like to share the solution cost between its users. We present algorithms for the problems ¿Connected Facility Location¿ and ¿Rent-or-Buy¿. These two problems are NP-hard, since they have as a particular case the minimum Steiner tree problem, which is a known NP-hard problem. In the first part of this work, we have the following question as motivation: ¿how to design a good network, i.e., one that satisfies all problem requirements and minimize the overall network construction cost?¿ In this part, approximation algorithms takes action. Once this cost is determinated, in the second part of the work, another question arises: ¿How to distribute this cost among all users that participate in the network in a ¿fair¿ way? In this part, we will use cost-sharing together with approximation algorithms techniques to answer this question Ver menos