The focus of attention problem

D. Goossens, S. Polyakovskiy, F.C.R. Spieksma, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


We consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations. The so-called Focus of Attention problem deals with the special case where every target is tracked by one pair of range sensors. We provide a complete complexity and approximability analysis of the Focus Of Attention problem: We establish its strong NP-hardness, and we construct a polynomial time approximation scheme for it.
Original languageEnglish
Title of host publicationProceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010)
PublisherSociety for Industrial and Applied Mathematics (SIAM)
ISBN (Print)978-089871701-3
Publication statusPublished - 2010
Event21st annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) - Austin, United States
Duration: 17 Jan 201019 Jan 2010
Conference number: 21


Conference21st annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
Abbreviated titleSODA'10)
Country/TerritoryUnited States


Dive into the research topics of 'The focus of attention problem'. Together they form a unique fingerprint.

Cite this