An Exact Algorithm for Maximum Entropy Sampling

By C. Ko, Jon Lee, Maurice Queyranne. 1995

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “[Ko et al., 1995] propose an exact, exponential branch-and-bound algorithm for finding the mode using greedy heuristics to build candidate sets; they tested their algorithm on problems up to N = 75, successfully finding optimal solutions in up to about an hour.”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, background): “While finding the information gain maximizer among , is NP-hard [24], it can be approximated by an efficient greedy algorithm.”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “g, see [32, 33, 34, 29, 6, 5]), and our results provide the first set of algorithms with provable constant-factor approximation guarantee (for cases in which the entropy is non-negative).”
Efficient Informative Sensing using Multiple Robots (2014, methodology): “Several alternative information criteria such as entropy (Ko et al., 1995), information disk model (Bai et al.”
Spatial sampling design under the infill asymptotic framework (2006, methodology): “See, for example, McBratney et al. (1981) and Yfantis et al. (1987), who provided empirical evidence that when using kriging as the prediction method and the average or maximum kriging variance as the criterion, the equilateral triangular grid is apparently nearly optimal.”
Near-optimal sensor placements in Gaussian processes (2005, unknown): “Let G be a graph, and let Σ be the matrix constructed in Ko et al. (1995).”
Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity (2017, background): “, finding the set of items with the highest probability, which is NP-hard [25].”
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies (2008, unknown): “For both entropy (Ko et al., 1995) and mutual information (this paper), this search has been shown to be NP-hard, hence efficient exact solutions are likely not possible.”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “However, the maximum a posteriori (MAP) problem arg maxY det(LY ) is NP-hard [14].”
Spatial sampling design for parameter estimation of the covariance function (2005, methodology): “Ko et al. (1995) use this method to solve a maximum entropy sampling problem of selecting 13 sites from 27 sites.”
Learning Determinantal Point Processes (2011, background): “Computing Y exactly is NP-hard (Ko et al., 1995), but we consider two approximations.”
Safe Exploration for Active Learning with Gaussian Processes (2015, background): “Note that Ko et al. (1995) showed that the problem of finding a finite set X opt is NP-hard.”
Handbook of Semidefinite Programming (2000, background): “Applications of this NP-Hard problem arise in environmental monitoring (see Ko, Lee and Queyranne [457]).”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, background): “In addition, we know that solving this problem exactly is NP-hard [24] (see also Lee [29] for a survey on known optimization techniques for the problem).”
Nonmyopic active learning of Gaussian processes: an exploration-exploitation approach (2007, methodology): “Maximizing (3.1) is NP-hard (Ko et al., 1995), so usually, a myopic (greedy) algorithm is used.”
Near-optimal Nonmyopic Value of Information in Graphical Models (2005, background): “…problem has been tackled with heuristic approaches, since even the unit cost has been shown to beNP-hard for multivariate Gaussian distributions [13], and a related formulation has been shown to beNPPPhard even for discrete distributions that can be represented by polytree graphical models [15].”
Spatial sampling design for prediction with estimated parameters (2006, methodology): “Ko et al. (1995) and Lee (1998) discussed an exact algorithm for maximum entropy sampling based on branch-and-bound methods that can find the exact solution that maximizes the entropy, and successfully solved a problem of selecting 13 from 27 sites.”
A Note on the Budgeted Maximization of Submodular Functions (2005, unknown): “Keywords: Submodular functions; Optimization; Constraints; Entropy maximization”
Optimal Value of Information in Graphical Models (2009, methodology): “Even for multivariate normal distributions, optimal Bayesian Experimental design is NP-hard (Ko, Lee, & Queyranne, 1995).”