This project contains the implementations of three approximation algorithms for solving maximum entropy sampling problem (MESP): greedy, local search and randomized sampling, which correspond to files greedy.py, local_search.py and randomized.py, respectively. Further, in the user.py file, we input the covariance matrix, carry out data preprocessing and define functions. In the frank_wolfe.py file, we implement the Frank-Wolfe algorithm to solve an upper bound for MESP. The test data is in Data124.dms giving a matrix of size 124 * 124. We test the instance in the datagen.py file.
For our paper "Approximation Algorithms for the Maximum Entropy Sampling Problem", and detailed implementation of the algorithms, see: https://arxiv.org/pdf/2001.08537.pdf