A quasi-polynomial algorithm for the Knapsack Problem

The main result of the paper is a quasi-polynomial algorithm for generating the extremal points (vertices) of the Knapsack Polytope. The complexity of this algorithm (for fixed dimension) is better than the complexity of all the known quasi-polynomial algorithms for this problem. The idea is similar to this one used by Haies and Larman. The present improvement is based on obtaining of new upper bounds for the number of the vertices of the Knapsack Polytope. The algorithm can be applied directly to solve the Knapsack Problem with arbitrary convex objective function.