  This work studies the combinatorial optimization problem of finding an
optimal core tensor shape, also called multilinear rank, for a size-constrained
Tucker decomposition. We give an algorithm with provable approximation
guarantees for its reconstruction error via connections to higher-order
singular values. Specifically, we introduce a novel Tucker packing problem,
which we prove is NP-hard, and give a polynomial-time approximation scheme
based on a reduction to the 2-dimensional knapsack problem with a matroid
constraint. We also generalize our techniques to tree tensor network
decompositions. We implement our algorithm using an integer programming solver,
and show that its solution quality is competitive with (and sometimes better
than) the greedy algorithm that uses the true Tucker decomposition loss at each
step, while also running up to 1000x faster.
