Easily Computable Facets of the Knapsack Polytope

Publisher Website
Google Scholar
Abstract
It is known that facets and valid inequalities for the knapsack polytope P can be obtained by lifting a simple inequality derived from each minimal cover. We study the computational complexity of such lifting. In particular, we show that the task of computing a lifted facet can be accomplished in O(ns) where s ≤ n is the cardinality of the minimal cover. Also, for a lifted inequality with integer coefficients, we show that the dual tasks of recognizing whether the inequality is valid for P or is a facet of P can be done within the same time bound.

This publication has 0 references indexed in Scilit: