Maximizing Determinants under Combinatorial Constraints
Speaker:
Aleksandar Nikolov, University of Toronto
Date and Time:
Wednesday, November 27, 2019 - 11:30am to 12:00pm
Location:
Fields Institute, Stewart Library
Abstract:
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.