Search

We introduce a new problem called Steiner Multi Cycle Problem that extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. In this problem we are given a complete weighted graph G=(V,E), which respects the triangle inequality, a collection of terminal sets {T_1,..., T_k}, where for each a in [k] we have a subset T_a of V and these terminal sets are pairwise disjoint. The problem is to find a set of disjoint cycles of minimum cost such that for each a in [k], all vertices of T_a belong to a same cycle. Our main interest is in a restricted case where |T_a| = 2, for each a in [k], which models a collaborative less-than-truckload problem with pickup and delivery. In this problem, we have a set of agents where each agent is associated with a set T_a containing a pair of pickup and delivery vertices. This problem arises in the scenario where a company has to periodically exchange goods between two different locations, and different companies can collaborate to create a route that visits all its pairs of locations sharing the total cost of the route. We show that even the restricted problem is NP-Hard, and present some heuristics to solve it. In particular, a constructive heuristic called Refinement Search, which uses geometric properties to determine if agents are close to each other. We performed computational experiments to compare this heuristic to a GRASP based heuristic. The Refinement Search obtained the best solutions in little computational time.

Orientador: Orlando Lee Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities Doutorado Ciência da Computação Doutor em Ciência da Computação FAPESP

In this paper we propose the Online Connected Facility Location problem (OCFL), which is an online version of the Connected Facility Location problem (CFL). The CFL is a combination of the Uncapacitated Facility Location problem (FL) and the Steiner Tree problem (ST). We give a randomized O(log2 n)-competitive algorithm for the OCFL via the sample-and-augment framework of Gupta, Kumar, Pál, and Roughgarden and previous algorithms for Online Facility Location (OFL) and Online Steiner Tree (OST). Also, we show that the same algorithm is a deterministic O(logn)-competitive algorithm for the special case of the OCFL with M?=?1, where M is a scale factor for the edge costs FUNDAÇÃO DE AMPARO À PESQUISA DO ESTADO DE SÃO PAULO - FAPESP CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO - CNPQ Fechado

Orientador: Lehilton Lelis Chaves Pedrosa Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Algoritmos de aproximação são algoritmos polinomiais para problemas de otimização que produzem soluções com uma certa garantia de qualidade. Para muitos problemas relevantes, não se conhecem algoritmos exatos eficientes e muitos deles são NP-difíceis. Desse modo, algoritmos de aproximação são uma alternativa para encontrar soluções boas para esses problemas. Neste trabalho, investigamos problemas que integram questões de inventário e roteamento. Mais especificamente, estudamos o Inventory Routing Problem (Problema de Estoque e Roteirização, IRP). Dado um ou mais depósitos, uma frota de veículos, um conjunto de clientes e um plano de horizonte de demandas de T períodos para cada cliente, o objetivo é formar entregas de forma que os veículos entreguem todas as demandas dos clientes a tempo, minimizando a soma dos custos de transporte e dos possíveis custos de armazenamento. Nossa contribuição é dividida em duas partes. Primeiro, estudamos o Inventory Access Problem (IAP), uma versão particular do IRP em que um único cliente enfrenta demandas em um horizonte de planejamento discreto e o objetivo é encontrar uma política de abastecimento que minimize a soma dos custos de transporte e armazenamento. Embora a versão não capacitada seja polinomial, apenas uma 3-aproximação é conhecida para o caso capacitado. Nós melhoramos esse fator para 2,619 e, como resultado direto, também diminuímos o melhor fator conhecido para o problema chamado Star Inventory Routing Problem with Facility Location (SIRPFL), que é uma extensão do IAP com vários depósitos e clientes e cujas soluções correspondem a rotas em formato de estrelas. Além disso, estudamos os casos capacitados do IAP e do SIRPFL em que todos os itens de uma mesma demanda devem ser entregues na mesma viagem e diminuímos os melhores fatores conhecidos também para essas versões. Em seguida, estudamos o Tree Joint Replenishment Problem (Tree JRP), outra versão particular do IRP em que um conjunto de clientes enfrenta demandas diárias por itens em um horizonte de planejamento discreto. As demandas são satisfeitas por itens já mantidos em estoque, que é reabastecido a partir de pedidos para um depósito que servem um subconjunto de clientes simultaneamente. No Tree JRP, a cadeia de abastecimento é representada por uma árvore cujas folhas são os clientes e o custo de um pedido para um subconjunto de clientes é determinado pelo custo de uma subárvore mínima que os conecta à raiz. O objetivo é decidir quando fazer os pedidos e quais clientes farão parte de cada pedido, de modo que os custos totais de transporte e armazenamento sejam minimizados. Neste trabalho, começamos o estudo da variante cujos pedidos têm capacidade limitada e fornecemos uma 5-aproximação baseada em arredondamento de PL. Destacamos que essa é a primeira aproximação tanto para o caso em que as demandas podem ser divididas em várias viagens, quanto para o caso em que a demanda de um período não pode ser dividida Abstract: Approximation algorithms are polynomial algorithms for optimization problems that produce solutions with a certain quality assurance. For many interesting optimization problems, no exact efficient algorithms are known and many of them are NP-hard. Therefore, approximation algorithms are an alternative to find good solutions for these problems. In this work, we investigate problems that integrate inventory and routing decisions. More specifically, we study the Inventory Routing Problem (IRP). Given one or more depots, a fleet of vehicles, a set of customers, and a demand planning horizon of T periods for each customer, the objective is to make trips in a way that the vehicles deliver all customer demands on time, minimizing the sum of transportation and storage costs. Our contribution is divided into two parts. First, we study the Inventory Access Problem (IAP), a particular version of the IRP where a single client faces demands in a discrete planning horizon and the goal is to find a supply policy that minimizes the sum of transportation and storage costs. Although the uncapacitated version is polynomial, only a 3-approximation is known for the capacitated case. We improved this factor to 2.619 and, as a direct result, we also improved the best factor for the problem called Star Inventory Routing Problem with Facility Location (SIRPFL), which is an extension of the IAP with many depots and customers and whose solutions have the format of a star. Moreover, we study the capacitated cases of IAP and SIRPFL in which all items of a single demand must be delivered by the same trip, and we improved the best-known factors for these versions as well. Next, we study the Tree Joint Replenishment Problem (Tree JRP), another particular version of the IRP where a set of customers faces daily demands for items in a discrete planning horizon. The demands are satisfied by items already held in stock and replenished by joint orders for a depot that serve a subset of customers simultaneously. In the Tree JRP, the supply chain is represented by a tree whose leaves are the customers, and the cost of an order for a subset of customers is determined by the cost of a minimum subtree that connects them to the root. The goal is to decide when to make the orders and which customers will be part of each order, so the total ordering and storage costs are minimized. In this work, we start the study of the variant where the orders have limited capacity, and provide a 5-approximation that is based on the LP rounding technique. We emphasize that this is the first approximation for the splittable version, when a demand can be divided into multiple trips, as well as for the unsplittable version, when one period's demand must be delivered in a single trip Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Fábio Luiz Usberti Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Problemas de roteamento em arcos têm por objetivo determinar rotas de custo mínimo que visitam um subconjunto de arcos de um grafo, com uma ou mais restrições adicionais. Esta tese estuda três problemas NP-difíceis de roteamento em arcos: (1) o problema de roteamento em arcos capacitado (CARP); (2) o problema de roteamento em arcos capacitado e aberto (OCARP); e (3) o problema do carteiro chinês com cobertura (CCPP). Apresentamos formulações matemáticas e métodos exatos e heurísticos para tratar computacionalmente esses problemas: (i) uma heurística construtiva gulosa e randomizada é proposta para o CARP; (ii) uma metaheurística de algoritmos genéticos híbrido e dois métodos de limitantes inferiores por programação linear inteira, um branch-and-cut e um baseado em redes de fluxos, são propostos para o OCARP; e (iii) um método exato branch-and-cut com desigualdades válidas e uma heurística construtiva são propostos para o CCPP. Extensivos experimentos computacionais utilizando instâncias de benchmark foram executados para demonstrar o desempenho dos métodos propostos em relação aos métodos da literatura, considerando tanto a qualidade das soluções obtidas quanto o tempo de processamento. Nossos resultados mostram que os métodos propostos são estado da arte. Os problemas estudados apresentam aplicações práticas relevantes: o CARP tem aplicações em coleta de lixo urbano e remoção de neve de estradas; o OCARP tem aplicações em roteamento de leituristas e na definição de caminhos de corte em chapas metálicas; e o CCPP tem aplicações em roteamento de leituristas com o uso de tecnologia wireless. A solução desses problemas remete à diminuição de custos logísticos, melhorando a competitividade das empresas Abstract: Arc routing problems aim to find minimum cost routes that visit a subset of arcs of a graph, with one or more side constraints. This thesis studies three NP-hard arc routing problems: (1) the capacitated arc routing problem (CARP); (2) the open capacitated arc routing problem (OCARP); and (3) the covering Chinese postman problem (CCPP). We present mathematical formulations and heuristic and exact methods to computationally solve these problems: (i) a greedy and randomized constructive heuristic is proposed for the CARP; (ii) a hybrid genetic algorithm metaheuristic and two linear integer programming lower bound methods, one based on branch-and-cut and one based on flow networks, are proposed for the OCARP; and (iii) an exact branch-and-cut method with valid inequalities and a constructive heuristic are proposed for the CCPP. Extensive computational experiments using benchmark instances were performed to demonstrate the performance of the proposed methods in comparison to the previous methods, regarding both quality of solutions and processing time. Our results show that the proposed methods are state-of-the-art. The studied problems have many relevant practical applications: the CARP has applications on urban waste collection and snow removal; the OCARP has applications on the routing of meter readers and the cutting of metal sheets; and last, the CCPP has applications on automated meter readers routing. The solution of these problems leads to the reduction of logistics costs, improving businesses competitiveness Doutorado Ciência da Computação Doutor em Ciência da Computação FAPESP 2016/00315-0

Orientadores: Cid Carvalho de Souza, Orlando Lee Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O problema do conjunto dominante m-eterno é um problema de otimização em grafos que tem sido muito estudado nos últimos anos e para o qual se têm listado aplicações em vários domínios. O objetivo é determinar o número mínimo de guardas que consigam defender eternamente ataques nos vértices de um grafo; denominamos este número o índice de dominação m-eterna do grafo. Nesta tese, estudamos o problema do conjunto dominante m-eterno: lidamos com aspectos de natureza teórica e prática e abordamos o problema restrito a classes especícas de grafos e no caso geral. Examinamos o problema do conjunto dominante m-eterno com respeito a duas classes de grafos: os grafos de Cayley e os conhecidos grafos de intervalo próprios. Primeiramente, mostramos ser inválido um resultado sobre os grafos de Cayley presente na literatura, provamos que o resultado é válido para uma subclasse destes grafos e apresentamos outros achados. Em segundo lugar, fazemos descobertas em relação aos grafos de intervalo próprios, incluindo que, para estes grafos, o índice de dominação m-eterna é igual à cardinalidade máxima de um conjunto independente e, por consequência, o índice de dominação m-eterna pode ser computado em tempo linear. Tratamos de uma questão que é fundamental para aplicações práticas do problema do conjunto dominante m-eterno, mas que tem recebido relativamente pouca atenção. Para tanto, introduzimos dois métodos heurísticos, nos quais formulamos e resolvemos modelos de programação inteira e por restrições para computar limitantes ao índice de dominação m-eterna. Realizamos um vasto experimento para analisar o desempenho destes métodos. Neste processo, geramos um benchmark contendo 750 instâncias e efetuamos uma avaliação prática de limitantes ao índice de dominação m-eterna disponíveis na literatura. Por m, propomos e implementamos um algoritmo exato para o problema do conjunto dominante m-eterno e contribuímos para o entendimento da sua complexidade: provamos que a versão de decisão do problema é NP-difícil. Pelo que temos conhecimento, o algoritmo proposto foi o primeiro método exato a ser desenvolvido e implementado para o problema do conjunto dominante m-eterno Abstract: The m-eternal dominating set problem is a graph-protection optimization problem that has been an active research topic in the recent years and reported to have applications in various domains. It asks for the minimum number of guards that can eternally defend attacks on the vertices of a graph; this number is called the m-eternal domination number of the graph. In this thesis, we study the m-eternal dominating set problem by dealing with aspects of theoretical and practical nature and tackling the problem restricted to specic classes of graphs and in the general case. We examine the m-eternal dominating set problem for two classes of graphs: Cayley graphs and the well-known proper interval graphs. First, we disprove a published result on the m-eternal domination number of Cayley graphs, show that the result is valid for a subclass of these graphs, and report further ndings. Secondly, we present several discoveries regarding proper interval graphs, including that, for these graphs, the m- eternal domination number equals the maximum size of an independent set and, as a consequence, the m-eternal domination number can be computed in linear time. We address an issue that is fundamental to practical applications of the m-eternal dominating set problem but that has received relatively little attention. To this end, we introduce two heuristic methods, in which we propose and solve integer and constraint programming models to compute bounds on the m-eternal domination number. By performing an extensive experiment to validate the features of these methods, we generate a 750-instance benchmark and carry out a practical evaluation of bounds for the m-eternal domination number available in the literature. Finally, we propose and implement an exact algorithm for the m-eternal dominating set problem and contribute to the knowledge on its complexity: we prove that the decision version of the problem is NP-hard. As far as we know, the proposed algorithm was the first developed and implemented exact method for the m-eternal dominating set problem Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES CNPQ 141964/2013-8

Orientadores: Zanoni Dias, Carla Negri Lintzmayer Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Calcular a distância evolucionária entre espécies é um problema importante da área de Biologia Computacional. Em várias abordagens, o cálculo dessa distância considera apenas rearranjos de genomas, os quais são conjuntos de mutações que alteram grandes trechos do genoma de um organismo. Assumindo que o genoma não possui genes duplicados, podemos representá-lo como permutações de números inteiros, em que cada elemento corresponde a um bloco conservado (região de alta similaridade entre os genomas comparados) e o sinal de cada elemento corresponde à orientação desse bloco. Ao usar permutações, o problema de transformar um genoma em outro é equivalente ao da Ordenação de Permutações por Operações de Rearranjo. A abordagem tradicional desse problema considera que todas as operações tem o mesmo custo e, assim, o objetivo é encontrar uma sequência mínima de operações que ordene a permutação. Entretanto, estudos indicam que algumas operações de rearranjo tem maior probabilidade de acontecer do que outras, fazendo com que abordagens em que operações possuem custos diferentes sejam mais realistas. Nas abordagens ponderadas, o objetivo é encontrar a sequência que ordena a permutação, de modo que a soma dos custos dos rearranjos dessa sequência seja mínimo. Neste trabalho, apresentamos algoritmos de aproximação para duas novas variações dos problemas da Ordenação de Permutações por Operações Ponderadas. A primeira variação utiliza uma função de custo correspondente à quantidade de fragmentações que a operação causa na permutação. A segunda variação utiliza uma função de custo proporcional ao tamanho da operação, além de adicionar a restrição de que as operações sejam curtas. Para cada uma das variações, foram considerados cinco problemas com os seguintes modelos de rearranjo: reversões sem sinais, reversões com sinais, transposições, reversões sem sinais e transposições, e reversões com sinais e transposições. Considerando os problemas da Ordenação de Permutações por Operações Ponderadas pelo Número de Fragmentações, apresentamos uma análise da relação entre os problemas não ponderados e essa variação, dois algoritmos de 2-aproximação para cada um dos cinco modelos de rearranjo, resultados experimentais desses algoritmos e limitantes inferiores e superiores para o diâmetro desses problemas. Além disso, apresentamos propriedades sobre permutações simples e um algoritmo de 1.5-aproximação assintótica para essa classe de permutações considerando reversões com sinais e/ou transposições. Para os problemas da Ordenação de Permutações por Operações Curtas Ponderadas pelo Tamanho, apresentamos uma análise da relação entre os problemas não ponderados e essa variação, algoritmos de aproximação com fator constante para cada um dos cinco modelos de rearranjo e resultados experimentais desses algoritmos. Além disso, fizemos uma análise do fator de aproximação dos algoritmos quando a função de custo é igual a l ^ alpha, onde l é o tamanho da operação e alpha > 1 é uma constante Abstract: One of the main problems in Computational Biology is to find the evolutionary distance among species. In most approaches, such distance only involves rearrangements, which are mutations that alter large pieces of the species' genome. Considering that the genome has no repeated genes, we can represent them as signed permutations, where each element corresponds to a synteny block (region of high similarity between the genomes compared) and the sign of each element corresponds to the orientation of such blocks. When using permutations, the problem of transforming one genome into another is equivalent to the problem of Sorting Permutations by Rearrangement Operations. The traditional approach is to consider that any rearrangement has the same probability to happen, and so the goal is to find a minimum sequence of operations which sorts the permutation. However, studies have shown that some rearrangements are more likely to happen than others, and so a weighted approach is more realistic. In a weighted approach, the goal is to find a sequence which sorts the permutations, such that the sum of the rearrangements' cost of that sequence is minimum. In this work, we presented approximation algorithms for two new variations of the Sorting Permutations by Weighted Operations problem. The first variation uses a cost function related to the amount of fragmentation caused by a rearrangement. The second variation uses a cost function proportional to the rearrangement's length, along with the constraint that operations must be short. For each variation, we considered five problems with the following rearrangement models: unsigned reversals, signed reversals, transpositions, unsigned reversals and transpositions, and signed reversals and transpositions. Considering the problems of Sorting Permutations by Fragmentation-Weighted Operations, we presented an analysis of the relation between the traditional approach and this variation, 2-approximation algorithms for each rearrangement model, experimental results of these algorithms, and upper and lower bounds for the diameter of these problems. Besides that, we showed properties of simple permutations and a 1.5-asymptotic approximation algorithm for this class of permutation considering signed reversals and/or transpositions. Considering the problems of Sorting Permutations by Length-Weighted Short Operations, we presented an analysis of the relation between the traditional approach and this variation, approximation algorithms with constant factor for each rearrangement model, and experimental results for these algorithms. Besides that, we analyzed the approximation factor for the algorithms we developed when the cost function is equal to l ^ alpha, where l is the rearrangement's length and alpha > 1 is a constant Mestrado Ciência da Computação Mestre em Ciência da Computação FAPESP 2017/16871-1 CNPQ 131182/2017-0

Orientador: Orlando Lee, Mário César San Felice Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Em problemas de otimização tradicionais, é comum pensar que soluções são construídas adquirindo recursos que perduram no tempo. Em contrapartida, no modelo de otimização com arrendamento se supõe que os recursos podem ser arrendados por diferentes períodos de tempo e que, devido a uma economia de escala, o custo-benefício em arrendar um recurso por períodos mais longos é maior. Esse modelo tem recebido alguma atenção recentemente, por modelar problemas tais como a alocação de recursos na nuvem. Nesta tese, estudamos o problema dos bilhetes de estacionamento, que é o problema fundamental de arrendamento, e propomos algumas generalizações. A primeira é o problema dos múltiplos bilhetes de estacionamento, que é uma generalização com múltiplos recursos idênticos. Esse problema pode ser resolvido em tempo polinomial. Mostramos também uma redução preservando aproximação para o problema original, que implica em um algoritmo online determinístico e outro probabilístico que são assintoticamente ótimos. A segunda variante proposta é o problema dos bilhetes de estacionamento em grupo, uma generalização do tipo aluguel-ou-compra, para a qual apresentamos uma 8-aproximação e um algoritmo online determinístico competitivo. A complexidade desse problema está em aberto, mas acreditamos que seja fracamente NP-difícil. Por fim, estudamos o problema dos bilhetes de estacionamento 2D, proposto por Hu, Ludwig, Richa e Schmid (2015). Os autores apresentaram um algoritmo com fator de aproximação constante e um algoritmo online determinístico competitivo para a versão hierárquica do problema, mas esses algoritmos consomem tempo pseudopolinomial. Nesta tese, mostramos como transformá-los em algoritmos de tempo polinomial. Mostramos também que o algoritmo de aproximação original funciona para a versão geral do problema, a qual provamos ser NP-difícil. Esses resultados implicam em algoritmos de aproximação e algoritmos online competitivos para variantes com arrendamento dos problemas da rede de Steiner, do aluguel-ou-compra e do projeto de redes em atacado, através da técnica de aproximação de métricas finitas por métricas arbóreas. Em particular, conseguimos melhorar o fator de aproximação para a versão com arrendamento do problema do aluguel-ou-compra com múltiplos destinos. Também revisamos algoritmos de aproximação para os problemas da localização de instalações com penalidades e do arrendamento de instalações, e apresentamos uma 3-aproximação para o problema do arrendamento de instalações com penalidades. Por fim, revisamos algoritmos de aproximação e algoritmos online para o problema da localização de instalações conectadas. Propomos quatro variantes com arredamento desse problema, e apresentamos algoritmos de aproximação e algoritmos online competitivos para o caso em que o (menor) fator de escala é 1. Também discutimos por que alguns dos algoritmos clássicos para o problema da localização de instalações conectadas e as técnicas de análise disponíveis na literatura não são suficientes para obter bons algoritmos para as variantes com arrendamento quando o (menor) fator de escala não é uma constante Abstract: In traditional optimization problems, we can think that a solution is built by acquiring resources that persist in time. In contrast, in the leasing optimization model, we assume that resources may be leased for different lengths of time and that, due to economies of scale, it is more cost-effective to lease a resource for longer periods. This model has received some attention recently, since it models problems such as cloud resource allocation. In this thesis, we study the parking permit problem, which is the seminal leasing problem, and we propose some generalizations. The first is the multi parking permit problem, which is a generalization with multiple identical resources. This problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields asymptotically optimal deterministic and randomized online algorithms. The second variant we propose is the group parking permit problem, a rent-or-buy generalization for which we give an 8-approximation algorithm and a deterministic competitive online algorithm. The complexity of this problem is open, but we believe it is weakly NP-hard. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid~(2015). They presented a constant approximation algorithm and a deterministic competitive online algorithm for the hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time. We also show that their original pseudo-polynomial offline algorithm works for the general version of the 2D parking permit problem, which we prove to be NP-hard. Those results yield approximation and competitive online algorithms for leasing variants of the Steiner network problem, the rent-or-buy problem, and the buy-at-bulk network design problem, by using the technique of approximating a finite metric by a tree metric. In particular, we improve the previous best approximation algorithm for the leasing version of the multi-commodity rent-or-buy-problem. We also review approximation algorithms for the facility location problem with penalties and the facility leasing problem, and we propose a 3-approximation algorithm for the facility leasing problem with penalties. Finally, we review approximation and competitive online algorithms for the connected facility location problem. Then we propose four leasing variants of this problem, and we give approximation and competitive online algorithms for each of them when the (smallest) scale factor is 1. We also discuss why some classical algorithms for the connected facility location problem and the available analysis techniques in the literature do not suffice to obtain good algorithms for the leasing variants when the (smallest) scale factor is not a constant Doutorado Ciência da Computação Doutor em Ciência da Computação CNPQ 142161/2014-4 FAPESP 2014/18781-1 CAPES