Advanced search
1 file | 225.84 KB Add to list

The focus of attention problem

(2016) ALGORITHMICA. 74(2). p.559-573
Author
Organization
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.
Keywords
Distributed sensors, Sensor assignment, Target tracking, SENSORS, TARGET TRACKING, APPROXIMATION ALGORITHMS, 3-DIMENSIONAL ASSIGNMENT PROBLEMS, Assignment problem, Complexity, Approximation, Intractable problem

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 225.84 KB

Citation

Please use this url to cite or link to this publication:

MLA
Goossens, Dries et al. “The Focus of Attention Problem.” ALGORITHMICA 74.2 (2016): 559–573. Print.
APA
Goossens, D., Polyakovskiy, S., Spieksma, F., & Woeginger, G. (2016). The focus of attention problem. ALGORITHMICA, 74(2), 559–573.
Chicago author-date
Goossens, Dries, Sergey Polyakovskiy, Frits Spieksma, and Gerhard Woeginger. 2016. “The Focus of Attention Problem.” Algorithmica 74 (2): 559–573.
Chicago author-date (all authors)
Goossens, Dries, Sergey Polyakovskiy, Frits Spieksma, and Gerhard Woeginger. 2016. “The Focus of Attention Problem.” Algorithmica 74 (2): 559–573.
Vancouver
1.
Goossens D, Polyakovskiy S, Spieksma F, Woeginger G. The focus of attention problem. ALGORITHMICA. Springer-Verlag; 2016;74(2):559–73.
IEEE
[1]
D. Goossens, S. Polyakovskiy, F. Spieksma, and G. Woeginger, “The focus of attention problem,” ALGORITHMICA, vol. 74, no. 2, pp. 559–573, 2016.
@article{6995573,
  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.},
  author       = {Goossens, Dries and Polyakovskiy, Sergey and Spieksma, Frits and Woeginger, Gerhard},
  issn         = {0178-4617},
  journal      = {ALGORITHMICA},
  keywords     = {Distributed sensors,Sensor assignment,Target tracking,SENSORS,TARGET TRACKING,APPROXIMATION ALGORITHMS,3-DIMENSIONAL ASSIGNMENT PROBLEMS,Assignment problem,Complexity,Approximation,Intractable problem},
  language     = {eng},
  number       = {2},
  pages        = {559--573},
  publisher    = {Springer-Verlag},
  title        = {The focus of attention problem},
  url          = {http://dx.doi.org/10.1007/s00453-014-9963-8},
  volume       = {74},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: