Logarithmic approximation bound for slab-constrained quadratic maximization

ID: logarithmic-approximation-bound-for-slab-constrained-quadratic-maximization

For spanning slab normals, apply the maximum of finitely many Rademacher linear forms bound to , whose squared norms are . Some sign vector has scaling denominator squared at most . Rademacher rounding for a semidefinite relaxation then produces a feasible vector of squared norm at least the displayed fraction of the SDP optimum. This is an existence guarantee from the probabilistic method.

New to topics? Read the docs here!