The Support of Integer Optimal Solutions
The Support of Integer Optimal Solutions
The support of a vector is the number of nonzero components. We show that given an integral $m\times n$ matrix $A$, the integer linear optimization problem $\max\{c^Tx : Ax = b, x \ge 0, x \in \mathbb{Z}^n\}$ has an optimal solution whose support is bounded by $2m \, \log (2 …