The Lasserre Rank of the Cropped Hypercube

G\'erard Cornu\'ejols; Vrishabh Patil; Jiaye Wei

In the authors' words

In an $n$ -dimensional cropped hypercube each of the $2^{n}$ cropping inequalities chops off a single corner of the $0$ -- $1$ hypercube by an $ℓ_{1}$ -distance $ρ$ . The case $ρ = 1/2$ has been extensively studied in the literature. This paper shows that the Lasserre rank of the $n$ -dimensional cropped hypercube where $ρ = 1/2$ , $n \geq 2$ , is the smallest integer $0 \leq t \leq n$ such that $Δ_{t} < 0$ in the recurrence $Δ_{- 1} = 1$ , $Δ_{0} = n - 1$ , $Δ_{t} = (n - 1) Δ_{t - 1} - t (n - t + 1) Δ_{t - 2}$ . It follows that the Lasserre rank can be computed in time $O (n^{2} lo g^{2} n)$ . Asymptotically, the rank is $\frac{n}{2} + c_{1/2} n + o (n)$ , where $c_{1/2}$ is the unique zero of a given function. Numerically, $c_{1/2} \approx 0.3825$ . In fact, we prove such results for any fixed $0 < ρ < 1$ .

Main resultThe abstract does not state a limitation.

The Lasserre Rank of the Cropped Hypercube

In the authors' words

More on Optimization that day

Stochastic Appointment Scheduling with Patient-and-Time-Dependent Probability Distributions

An Exact Algorithm for the Max-Min Covering Location Blocker Problem

From Frequentist to Bayesian Contextual Optimization

SWAP: A Scalable, Warm-Startable, Anytime Permutation Solver for Optimal Transport

Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization