Gradient elements of the knapsack polytope

Abstract

The knapsack problem is a classical NP-hard problem of special interest in combinatorial mathematics and complexity theory. Particularly interesting are the properties of the knapsack problem domain. In this paper we study the set of gradient elements of the knapsack polytope. They are related with the well-known greedy algorithm for finding approximate solutions to the optimization knapsack problem and constitute an important subset of the extremal elements (vertices) of the knapsack polytope. We obtain a tight bound for the number of distinct gradient elements, which is an exponential function of the problem dimension. We also use the greedy-algorithmic approach and the concept of gradient elements to devise a polynomial algorithm for a large subclass of a linear Diophantine problem which is a variant of the knapsack problem. Some optimization issues related to the problems considered are discussed as well.