Integral Near-optimal Solutions to Certain Classes of Linear Programming Problems |
Contents
BACKGROUND | 8 |
INTEGER ROUNDING AND POLYHEDRAL DECOMPOSITION | 21 |
8 | 44 |
5 other sections not shown
Common terms and phrases
antiblocking pair antiblocking theory anticliques assembly tree assume bipartite graph Chapter combinatorial constraint matrix constraint system convex combination convex hull decomposition property holds denote directed graph Edmonds extreme solutions feasible flow feasible solution finite Fulkerson 1970 Fulkerson and Weinberger G is perfect holds for II(B,w implies incidence matrix incidence vectors independent sets induction integer programming problem integral extreme points integral optimal solution integral points integral polymatroid integral vector IRD holds Lemma Let G linear programming problem loopless M₁ M₂ matrix whose rows matroid max-min theorems maximal min-max equality holds minimum number multiple edges nonempty nonnegative integers nonnegative matrix optimal integral solution optimal value pair of matrices perfect graphs polyhedron positive integer Proof real numbers result is clear rounding property rounding results solution of value submatrix supply-demand network Theorem II.1.1 totally unimodular matrix Trotter and Weinberger Weinberger 1976 zero columns zero rows