Optima of dual integer linear programs
type: Item
instance of: scholarly article
title: Optima of dual integer linear programs
zbMATH Open document ID: 0648.90054
DOI: 10.1007/BF02122549
author: Ron Aharoni
author: Nathan Linial
author: P. Erdős
published in: Combinatorica
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4059116
zbMATH Keywords: pair of linear programs
zbMATH Keywords: packing
zbMATH Keywords: covering integer linear programs
Wikidata QID: Q105659276
reviewed by: Z. J. Liu
MaRDI profile type: Publication
cites work: Maximum degree and fractional matchings in uniform hypergraphs
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Decomposition of regular matroids
full work available at URL: https://doi.org/10.1007/bf02122549
OpenAlex ID: W2093321189
description: scientific article; zbMATH DE number 4059116