Optima of dual integer linear programs (Q1105488): Difference between revisions

Let \(A\) be a 0-1 matrix of dimension \(n\cdot m\). Consider the following pair of linear programs \[ \text{(L)}\quad \max x\cdot 1,\quad Ax\leq 1,\quad x\geq 0;\quad \text{(D)}\quad \min y\cdot 1,\quad yA\geq 1,\quad y\geq 0. \] If integral solution constraints are added, they become dual pairs of packing and covering integer linear programs. Let \(z\) and \(Z\) be the integral optimum of (L) and (D), and q the common rational optimum of (L) and (D). The main results are that a tight inequality relating \(z\) and \(q\), and a best possible bound between \(z\) and \(Z\) can be found in the following form: \[ z\geq \frac{q^2}{n-(f-1)q^2/m}\geq q^2/n, \] \[ Z\leq \begin{cases} \min(n,3g) & \text{if } m>e(nz)^{1/2}, \\ m & \text{if }m<e(nz)^{1/2}, \end{cases} \] where \(f\) is the least column sum of \(A\), and \(g(nz\ln(m/(nz)^{1/2})^{1/2}\). At end of the paper the autor suggest further interesting directions for research.