## Integral near-optimal solutions to certain classes of linear programming problems |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

BACKGROUND | 8 |

INTEGER ROUNDING AND POLYHEDRAL DECOMPOSITION | 21 |

EXAMPLES | 41 |

2 other sections not shown

### Common terms and phrases

antiblocking pair assembly tree assume bipartite graph blocking matrix Chapter combinatorial constraint matrix constraint system convex combination convex hull decomposition property holds denote directed graph Edmonds l970 extreme solutions feasible flow feasible solution finite Fulkerson and Weinberger Fulkerson l970 holds for n(B,w identity matrix implies incidence matrix incidence vectors integer programming problem integral extreme points integral optimal solution integral points integral polymatroid integral vector IRD holds Lemma Let G linear programming problem loopless matrix whose rows matroid maximal min-max equality holds minimum number multiple edges nonempty nonnegative integers nonnegative matrices nonnegative matrix optimal integral solution optimal value pair of matrices perfect graphs positive integer Proof real numbers result is clear rounding property rounding results solution of value solution to r(A,w submatrix supply-demand network Theorem III.3.l totally unimodular matrix Trotter and Weinberger w e z Weinberger l975 x e kP zero columns zero rows