Defesa de Mestrado de Marcelo Pinheiro Leite Benedito

Título do Trabalho
Approximation Algorithms for Hub Location Problems
Candidato(a)
Marcelo Pinheiro Leite Benedito
Nível
Mestrado
Data
Add to Calender 2018-07-31 00:00:00 2018-07-31 00:00:00 Defesa de Mestrado de Marcelo Pinheiro Leite Benedito Approximation Algorithms for Hub Location Problems Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 IC 2
Orientador(a)
Lehilton Lelis Chaves Pedrosa
Banca Examinadora

Condição

Titulares  - Professores Doutores

Unidade/Instituição

Presidente

Lehilton Lelis Chaves Pedrosa

IC/UNICAMP

Membro

Luis Augusto Angelotti Meira

FT/UNICAMP

Membro

Cid Carvalho de Souza

IC/UNICAMP

 

Condição

Suplentes  - Professores Doutores

Unidade/Instituição

Suplente

Fábio Luiz Usberti

IC/UNICAMP

Suplente

Thiago de Paulo Faleiros

CIC/UnB

Resumo

 

No Problema de Localização e Alocação de Terminais, a entrada é um espaço métrico composto por clientes, localidades e um conjunto de pares de clientes; uma solução é um subconjunto das localidades, onde serão abertos terminais, e uma atribuição de cada par de clientes à uma rota, que começa no primeiro cliente, passando em um ou dois terminais, e terminando no segundo cliente. O objetivo é encontrar uma solução que minimize o tamanho de todas as rotas somado com o custo de abertura de terminais. Os algoritmos de aproximação da literatura consideram apenas o caso em que o conjunto de terminais abertos é dado como parte da entrada, e o problema se torna atribuir clientes aos terminais; ou então quando o espaço é definido em classes especiais de grafos. Neste trabalho, apresentamos o primeiro algoritmo de aproximação com fator constante para o problema de, simultaneamente, escolher localidades para abrir terminais e atribuir clientes à estes.
A primeira parte desta dissertação cria algoritmos de aproximação para diversas variantes do problema. A estratégia principal é reduzir os problemas de localização e alocação de terminais aos problemas clássicos de localidades, como o problema de localização de instalações e o problema das k-medianas. A redução transforma uma instância de localização e alocação de terminais em uma instância de um destes problemas, que então é resolvida usando famosos algoritmos de aproximação. A saída do algoritmo induz uma solução para o problema original, com uma perda constante no fator de aproximação.
Na segunda parte, o foco é o Problema de Localização e Alocação Única de Terminais (SAHLP), que é uma variação em que cada cliente deve estar conectado a apenas um terminal, além de não haver limite na quantidade de terminais abertos. A principal contribuição é um algoritmo 2.48-aproximado para o SAHLP, baseado em arredondamento de uma nova formulação de programa linear para o problema. O algoritmo é composto por duas fases: na primeira, a solução fracionária é escalada e um subconjunto de terminais é aberto, e na segunda, atribuímos clientes aos terminais abertos. A primeira fase segue o formato padrão de filtering para problemas de localidades. A segunda, no entanto, exigiu o desenvolvimento de novas ideias e é baseada em múltiplos critérios para realizar a atribuição. A principal técnica atribui cada cliente ao terminal aberto mais próximo, se este estiver em sua vizinhança; caso contrário, o cliente se conecta ao terminal que melhor balanceia múltiplos custos, relacionados à distância entre eles.