Exact characterization conjecture for boundary hyperplane covers of quadratic sets

Let B={x:x21}B=\{\mathbf{x}:\|\mathbf{x}\|_2\leq 1\} and C={x:g(x)0}C=\{\mathbf{x}:g(\mathbf{x})\leq 0\}, where gg is a quadratic polynomial. Suppose that gg has one of the forms

g(x)=α(i=1nxi21)+h1(x)h2(x)g(\mathbf{x})=\alpha\left(\sum_{i=1}^n x_i^2-1\right)+h_1(\mathbf{x})h_2(\mathbf{x})

or

g(x)=α(i=1nxi21)+h1(x),g(\mathbf{x})=\alpha\left(\sum_{i=1}^n x_i^2-1\right)+h_1(\mathbf{x}),

where α0\alpha\neq 0 and the hih_i are non-trivial affine functions. Exact characterization conjecture. Theorem~ holds as an if and only if: BB and CC have a Boundary Hyperplane Cover if and only if gg has one of these two forms, with the hyperplanes given by hi(x)=0h_i(\mathbf{x})=0 as appropriate. The theorem supplies the sufficient direction; proving the converse requires algebraic tools to show that no other quadratic intersections have the Boundary Hyperplane Cover property.

Sources & referencesView supporting material

Primary source

Robert Hildebrand and Adrian Göß, “Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover”, arXiv:2409.05308 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.