The focus of attention problem

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)559-573
Number of pages15
JournalAlgorithmica
Volume74
Issue number2
DOIs
Publication statusPublished - 1 Feb 2016

Keywords

  • Approximation
  • Assignment problem
  • Complexity
  • Distributed sensors
  • Intractable problem
  • Sensor assignment
  • Target tracking

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

Cite this