An Exact Algorithm for Maximum Entropy Sampling

Chun-Wa Ko, Jon Lee and Maurice Queyranne
Additional contact information
Chun-Wa Ko: Rutgers University, New Brunswick, New Jersey
Jon Lee: University of Kentucky, Lexington, Kentucky
Maurice Queyranne: University of British Columbia, Vancouver, British Columbia, Canada

Operations Research, 1995, vol. 43, issue 4, 684-691

Abstract: We study the experimental design problem of selecting a most informative subset, having prespecified size, from a set of correlated random variables. The problem arises in many applied domains, such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations, and possibly, at different times. Information is measured by “entropy.” In the Gaussian case, the problem is recast as that of maximizing the determinant of the covariance matrix of the chosen subset. We demonstrate that this problem is NP-hard. We establish an upper bound for the entropy, based on the eigenvalue interlacing property, and we incorporate this bound in a branch-and-bound algorithm for the exact solution of the problem. We present computational results for estimated covariance matrices that correspond to sets of environmental monitoring stations in the United States.

Keywords: facilities/equipment planning; location of environmental monitoring stations; programming; nonlinear combinatorial optimization; statistics; maximum entropy sampling (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.4.684 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:4:p:684-691

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().