Facets of the Knapsack Polytope from Minimal Covers.
Abstract
In this paper the authors give easily computable best upper and lower bounds on the coefficients of facets of the knapsack polytope associated with minimal covers. For some coefficients the upper bounds are equal to the lower bounds; for the others the two bounds differ by 1. A necessary and sufficient condition is given for all lower bounds to be equal to the corresponding upper bounds, i.e. for the facet associated with the given minimal cover to be unique. Also, a partial order is defined on the set of minimal covers and it is shown that all facets associated with minimal covers can be obtained from weak covers; but that each facet obtainable from several ordered minimal covers is easiest to compute from the strongest one.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1974
- Accession Number
- ADA009265
Entities
People
- Egon Balas
- Eitan Zemel
Organizations
- Carnegie Mellon University