Search

Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time $f(\alpha)$-competitive algorithm, where $f(\alpha)\in [1.618+\epsilon,2]$ depends on the approximation ratio $\alpha$ for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than $1.5$-competitive. Furthermore, we give polynomial-time $4/3$-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds., Comment: An extended abstract appears in the proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021)

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