  Measurements and sensing implementations impose certain cost in sensor
networks. The sensor selection cost optimization is the problem of minimizing
the sensing cost of monitoring a physical (or cyber- physical) system. Consider
a given set of sensors tracking states of a dynamical system for estimation
purposes. For each sensor assume different costs to measure different
(realizable) states. The idea is to assign sensors to measure states such that
the global cost is minimized. The number and selection of sensor measurements
need to ensure the observability to track the dynamic state of the system with
bounded estimation error. The main question we address is how to select the
state measurements to minimize the cost while satisfying the observability
conditions. Relaxing the observability condition for structurally cyclic
systems, the main contribution is to propose a graph theoretic approach to
solve the problem in polynomial time. Note that, polynomial time algorithms are
suitable for large-scale systems as their running time is upper-bounded by a
polynomial expression in the size of input for the algorithm. We frame the
problem as a linear sum assignment with solution complexity of O(m3).
