File(s) under permanent embargo
The focus of attention problem
journal contribution
posted on 2016-02-01, 00:00 authored by D Goossens, Sergey PolyakovskiySergey Polyakovskiy, F C R Spieksma, G J WoegingerWe 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.
History
Journal
AlgorithmicaVolume
74Issue
2Pagination
559 - 573Publisher
SpringerLocation
New York, N.Y.Publisher DOI
ISSN
0178-4617eISSN
1432-0541Language
engPublication classification
C Journal article; C1.1 Refereed article in a scholarly journalCopyright notice
2014, Springer Science+Business Media New YorkUsage metrics
Keywords
target trackingdistributed sensorssensor assignmentassignment problemcomplexityapproximationintractable problemScience & TechnologyTechnologyPhysical SciencesComputer Science, Software EngineeringMathematics, AppliedComputer ScienceMathematicsAPPROXIMATION ALGORITHMSASSIGNMENT PROBLEMSDistributed Computing