We are given the following linear program:
minimize $\mathbf{1}^T x$ subject to $Ax\geq \mathbf{1}, x\geq \mathbf{0}$.
We know that $A\in\{0,1\}^{m\times n}$, and that each row and column contains at least one nonzero entry. It exist both an optimal solution $x^*$ and an optimal integer solution $x'$ (meaning all its components are integer).
It is asked to prove that the following holds $$\mathbf{1}^T x'\leq\mathbf{1}^T x^*\ln(m)+1$$
What it can be seen is that $x^*_i\in[0,1]$, and that $x'_i\in\{0,1\}$, but I have no idea on how to prove that inequality.
Any help would be much appreciated! Thank you