Full text
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (695kB) | Preview |
Solving the minimum vertex floodlight problem with hybrid metaheuristics
Citation
Hernández Peñalver, Gregorio and Bajuelos Domínguez, Antonio Leslie and Martins, Ana Mafalda and Canales Cano, Santiago (2011). Solving the minimum vertex floodlight problem with hybrid metaheuristics. In: "Proc. of XIV Spanish Meeting on Computacional Geometry,", 27/06/2011 - 30/06/2011, Alcalá de Henares, Madrid. ISBN 2014-232. pp. 83-86.
Description
| Title: | Solving the minimum vertex floodlight problem with hybrid metaheuristics |
|---|---|
| Author/s: |
|
| Item Type: | Presentation at Congress or Conference (Article) |
| Event Title: | Proc. of XIV Spanish Meeting on Computacional Geometry, |
| Event Dates: | 27/06/2011 - 30/06/2011 |
| Event Location: | Alcalá de Henares, Madrid |
| Title of Book: | XIV Spanish Meeting on Computational Geometry : Alcalá de Henares, June 27-30, 2011 |
| Date: | June 2011 |
| ISBN: | 2014-232 |
| Subjects: | |
| Faculty: | Facultad de Informática (UPM) |
| Department: | Matemática Aplicada |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
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.
More information
| Item ID: | 19278 |
|---|---|
| DC Identifier: | https://oa.upm.es/19278/ |
| OAI Identifier: | oai:oa.upm.es:19278 |
| Official URL: | http://hdl.handle.net/2072/200199 |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 23 Sep 2013 17:10 |
| Last Modified: | 21 Apr 2016 17:32 |
