08-04-2011
SeminárIO – seminários em Investigação Operacional no CMA
"Conjuntos convexos contendo pontos discretos"
Miguel Constantino
(Centro de Investigação Operacional - Faculdade de Ciências da Universidade de Lisboa)
Resumo:
No contexto da optimização espacial (2d e 3d) surge o seguinte problema. Dados n pontos, com pesos positivos ou negativos associados, pretende-se determinar um conjunto convexo cuja soma dos pesos dos pontos que contém é máxima. Mostra-se que o problema é NP-difícil no espaço tri-dimensional e apresenta-se um algoritmo polinomial para o caso bi-dimensional.
