Open Collections

Applying record value theory in combinatorial optimization with application to environmental statistics

University of British Columbia

We consider the problem of optimal subset selection from a set of correlated random variables. In particular, we consider the associated combinatorial optimization problem of maximizing the determinant of a symmetric positive semidefinite matrix that characterizes the chosen subset. This problem arises in many domains, such as experimental designs, regression modelling, and environmental statistics. In this thesis, we attempt to establish an efficient polynomial-time algorithm for approximating the optimal solution to the problem. Firstly, we employ determinantal point processes, a special class of spatial point processes, to develop an easy-to-implement sampling-based stochastic search algorithm for the task of finding approximations to the combinatorial optimization problem. Secondly, we establish theoretical tools for assessing the quality of those approximations using statistical results from record value theory, the study of record values and related statistics from a sequence of observations.

Text

2018-08-14

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/66768

Statistics

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/