Skip to main content
1 of 3
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Smallest box with an integer lattice point in a polytope?

Given an integer lattice $\mathcal L\subseteq\mathbb Z^n$ represented by basis $\mathcal B$ and an integer linear program $Ax\leq b$ where $x\in\mathbb Z^n$ is unknown with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a tight upper bound for $$\min_{x\in\mathcal L:Ax\leq b}\prod_{i=1}^n(1+|x_i|)?$$

What about the simplest case of $\mathcal L=\mathbb Z^n$?

Turbo
  • 13.9k
  • 1
  • 27
  • 76