Defesa de Doutorado de Murilo Santos de Lima

Título do Trabalho
Parking Permit and Network Leasing Problems
Candidato(a)
Murilo Santos de Lima
Nível
Doutorado
Data
Add to Calender 2018-05-11 00:00:00 2018-05-11 00:00:00 Defesa de Doutorado de Murilo Santos de Lima Parking Permit and Network Leasing Problems Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
11:00
Local
Sala 85 IC 2
Orientador(a)
Orlando Lee
Banca Examinadora

Condição

Titulares  (Professores Doutores)

Unidade/Instituição

Orientador/Presidente

Orlando Lee

IC/UNICAMP

Membro

Aritanan Borges Garcia Gruber

CMCC/UFABC

Membro

Marco Serpa Molinaro

DI/PUC-Rio

Membro

Eduardo Candido Xavier

IC/UNICAMP

Membro

Lehilton Lelis Chaves Pedrosa

IC/UNICAMP

 

Condição

Suplentes (Professores Doutores)

Unidade/Instituição

Suplente

Flávio Keidi Miyazawa

IC/UNICAMP

Suplente

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Suplente

José Coelho de Pina Junior

IME/USP

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, há mais custo-benefício em arrendar um recurso por períodos mais longos. 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-copra 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.