On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Pricing and Moment Problems
We study continuous quadratic submodular minimization with bounds and provide a polynomially sized semidefinite relaxation, which is provably tight for dimension n <= 3. Via an explicit counterexample for n = 4, we show that the relaxation is not tight in general, although it remains empirically tight on randomly generated instances. We apply the relaxation … Read more