Solving the minimum vertex floodlight problem with hybrid metaheuristics

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:
  • Hernández Peñalver, Gregorio
  • Bajuelos Domínguez, Antonio Leslie
  • Martins, Ana Mafalda
  • Canales Cano, Santiago
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (695kB) | Preview

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM