Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 648.90054
Autor: Aharoni, R.; Erdös, Paul; Linial, N.
Title: Optima of dual integer linear programs. (In English)
Source: Combinatorica 8, No.1, 13-20 (1988).
Review: Let A be a 0-1 matrix of dimension n· m. Consider the following pair of linear programs (L) max x· 1, Ax \leq 1, x \geq 0; (D) max y· 1, yA \geq 1, 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{q2}{n-(f-1)q2/m} \geq q2/n,
| Z \leq | max(n,3g) if m > e(nz) ½, |
| m if m < e(nz) ½, |
where f is the least column sum of A, and g(nz ln(m/(nz) ½) ½. At end of the paper the autor suggest further interesting directions for research.
Reviewer: Z.Liu
Classif.: * 90C10 Integer programming
90C27 Combinatorial programming
05C70 Factorization, etc.
90C05 Linear programming
Keywords: pair of linear programs; packing; covering integer linear programs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag