  Given a linear dynamical system, we consider the problem of selecting (at
design-time) an optimal set of sensors (subject to certain budget constraints)
to minimize the trace of the steady state error covariance matrix of the Kalman
filter. Previous work has shown that this problem is NP-hard for certain
classes of systems and sensor costs; in this paper, we show that the problem
remains NP-hard even for the special case where the system is stable and all
sensor costs are identical. Furthermore, we show the stronger result that there
is no constant-factor (polynomial-time) approximation algorithm for this
problem. This contrasts with other classes of sensor selection problems studied
in the literature, which typically pursue constant-factor approximations by
leveraging greedy algorithms and submodularity of the cost function. Here, we
provide a specific example showing that greedy algorithms can perform
arbitrarily poorly for the problem of design-time sensor selection for Kalman
filtering.
