${\ell }_p$-Norm Maximization over Zonotopes Is W[1]-Hard

Yang Cao, Haoran Qi, Hanzhi Wang

We study ${\ell }_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mat…