Exact and Approximation Algorithms for Entropy Sampling and Stochastic Optimization

Abstract

In this thesis, we study three combinatorial problems. In the first half, we focus on a deterministic combinatorial optimization problem called the maximum-entropy sampling problem (MESP). The MESP seeks to find the maximum log-determinant principal submatrix of a given positive-semidefinite matrix C. For cases where C (or its inverse) is tridiagonal, we develop an efficient dynamic-programming algorithm and extend this approach to matrices where the graph support of C is a spider graph with a bounded number of legs. We also introduce the concept of using a tridiagonal mask M to obtain a fast upper-bounding method for the MESP. To complement this, we provide an R package tailored for handling multivariate precipitation chemistry data. This package facilitates temporal modeling of data from the National Atmospheric Deposition Program / National Trends Network, yielding covariance matrices essential for the evaluation of MESP algorithms.

The second half of the thesis addresses stochastic combinatorial optimization problems, where uncertainty is introduced to some input parameters. We present new approximation algorithms for the adaptive submodular cover and stochastic minimum query problems. We address the problem of minimizing the cost to cover adaptive-submodular functions and present a 4(1+ln Q)-approximation algorithm, where Q represents the goal value of the covering functions. We also show a guarantee for a more general objective, the p-th moment of the cost of our policy. For the p-th moment, we show a (p+1)^{(p+1)}(1 + ln(Q))^p-approximation.

In the stochastic minimum query problem, we seek to find a value within delta of the minimum (or maximum) over n independent random variables. We call this value the delta-minimum and we are also interested in a variant of the problem where we seek to identify the delta-minimizer which is the interval that contains a delta-minimum. For each random variable we query, we incur some cost and the goal is to minimize the expected query costs while identifying the delta-minimum (or delta-minimizer). For uniform query costs, we develop a 4-approximation algorithm applicable to both $delta$-minimum and delta-minimizer variants. For non-uniform costs, we achieve a 5.83-approximation and 7.47-approximation for the problem of finding the delta-minimum and delta-minimizer, respectively. Our algorithms, based on non-adaptive querying, effectively upper bound the adaptivity gap.