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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.