New Exact Algorithms for Planar Maximum Covering Location by Ellipses Problems

• Ano de defesa: 2020
• Autor(a) principal: Tedeschi, Danilo Françoso
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Cobertura planar por ellipses, Algoritmos exatos; Combinatorial optimization; Exact algorithms; Otimização combinatorial; Planar covering by ellipses; Planar maximal covering location problem
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23072020-154136/

Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to place fixed shape ellipses on the plane to cover demand points maximizing a function depending on the value of covered points. We propose new exact algorithms for two versions of this problem, one where the ellipses have to be parallel to the coordinate axis, and another where they can be freely rotated. Besides finding optimal solutions for previously published instances, including the ones where no optimal solution was known, both algorithms proposed by us were able to obtain optimal solutions for some new larger instances having with up to seven hundred demand points and five ellipses.