UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International