Optima of dual integer linear programs (Q1105488): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Ron Aharoni / rank | |||
Property / author | |||
Property / author: Nathan Linial / rank | |||
Property / reviewed by | |||
Property / reviewed by: Z. J. Liu / rank | |||
Revision as of 09:43, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optima of dual integer linear programs |
scientific article |
Statements
Optima of dual integer linear programs (English)
0 references
1988
0 references
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.
0 references
pair of linear programs
0 references
packing
0 references
covering integer linear programs
0 references