Maximizing Determinants under Combinatorial Constraints
Given a set of vectors v_1, …, v_n in d-dimensional space, and the corresponding rank-one PSD matrices v_i v_i^T, we consider the problem of selecting a subset S of the rank-one matrices whose sum has maximum determinant, under various combinatorial constraints on S. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning. I will outline some of these connections, and describe how randomized rounding, convex optimization, and the theory of real stable / log-concave polynomials lets us design approximation algorithms for this problem.