Hardness of A/E-Design under Partition Constraints

Abstract

We consider the A/E-design problem under partition constraints: Given vectors $v_1,\dots ,v_N\in {\mathbb{R}}^d$ and a partition matroid on $[N]$, find a base $S$ of the matroid that minimizes $\tr(M(S)^{-1})$ or ${\lambda }_{\max }(M(S{)}^{-1})$ where $M(S)={\sum }_{i\in S}{v}_i{v}_i^{\top }$. In contrast to D-design, where good estimation and approximation guarantees are known as a function of $d$, we show that no reasonable approximation exists for A/E-design. This answers a question of Brown, Laddha and Singh. The proof is based on an elementary reduction from three-dimensional matching.