Gradient elements of the knapsack polytope |
| |
Authors: | V E Brimkov R P Barneva |
| |
Affiliation: | Department of Mathematics, Eastern Mediterranean University, Famagusta, TRNC,?Via Mersin 10, Turkey.?e-mail: valentin.brimkov@emu.edu.tr?e-mail: reneta.barneva@emu.edu.tr, TR
|
| |
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.
Received: September 1999 / Accepted: December 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|