3
$\begingroup$

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

$\endgroup$

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.