Solving the minimum vertex floodlight problem with hybrid metaheuristics
| Data(s) |
01/06/2011
|
|---|---|
| Resumo |
In this paper we propose four approximation algorithms (metaheuristic based), for the Minimum Vertex Floodlight Set problem. Urrutia et al. [9] solved the combinatorial problem, although it is strongly believed that the algorithmic problem is NP-hard. We conclude that, on average, the minimum number of vertex floodlights needed to illuminate a orthogonal polygon with n vertices is n/4,29. |
| Formato |
application/pdf |
| Identificador | |
| Idioma(s) |
eng |
| Publicador |
Facultad de Informática (UPM) |
| Relação |
http://oa.upm.es/19278/1/INVE_MEM_2011_121568.pdf http://hdl.handle.net/2072/200199 info:eu-repo/semantics/altIdentifier/doi/null |
| Direitos |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/openAccess |
| Fonte |
XIV Spanish Meeting on Computational Geometry : Alcalá de Henares, June 27-30, 2011 | Proc. of XIV Spanish Meeting on Computacional Geometry, | 27/06/2011 - 30/06/2011 | Alcalá de Henares, Madrid |
| Palavras-Chave | #Informática |
| Tipo |
info:eu-repo/semantics/conferenceObject Ponencia en Congreso o Jornada PeerReviewed |
