The BoxContZonotope NP-hardness conjecture

Let a1,,amQna_1,\ldots,a_m\in\mathbb{Q}^n and let ν[0,)Q\nu\in[0,\infty)\cap\mathbb{Q}. BoxContZonotope conjecture. Deciding whether there exists a rectangular box BB such that

j=1m[aj,aj]B,voln(B)ν\sum_{j=1}^m[-a_j,a_j]\subset B,\qquad \operatorname{vol}_n(B)\leq\nu

is NP\mathbb{NP}-hard. The problem is introduced as a further source of computational intractability in determining Λ(P)\Lambda(P), beyond volume computation alone; no proof or resolution is supplied.

Sources & referencesView supporting material

Primary source

Stefano Campi, Peter Gritzmann and Paolo Gronchi, “On the reverse Loomis-Whitney inequality”, arXiv:1607.07891 (2017).

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.