The Focus of Attention Problem
Files
(Restricted Access)
Date
2016
Authors
Goossens, D.
Polyakovskiy, S.
Spieksma, F.
Woeginger, G.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Algorithmica: an international journal in computer science, 2016; 74(2):559-573
Statement of Responsibility
Dries Goossens, Sergey Polyakovskiy, Frits C.R. Spieksma, Gerhard J. Woeginger
Conference Name
Abstract
We consider systems of small, cheap, simple sensors that are organized in a distributed network and used for estimating and tracking the locations of targets. The objective is to assign sensors to targets such that the overall expected error of the sensors’ estimates of the target locations is minimized. The so-called focus of attention problem (FOA) deals with the special case where every target is tracked by one pair of range sensors. The resulting computational problem is a special case of the axial three-index assignment problem, a well-known fundamental problem in combinatorial optimization. We provide a complete complexity and approximability analysis of the FOA problem: we establish strong NP-hardness and the unlikeliness of an FPTAS, we identify polynomially solvable special cases, and we construct a sophisticated polynomial time approximation scheme for it.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Springer Science+Business Media New York 2014