Some Complexity Issues in a Class of Knapsack Problems : What Makes a Knapsack Problem 'Hard'?

We propose a new class of knapsack problems by assiuning that the sizes of the items to be put into a knapsack are known to be elements 0f a given subset S of the positive integers Z'^. The set S is treated as a parameter. We show that the family of knapsack problems obtained by varying the parameter S in the power set of Z'^ contains polynomially solvable problems and NP-complete problems, even when we restrict S to the class of polynomially recognizable sets

MoreLess

Year of publication:	2010
Authors:	Krass, D. ; Sethi, Suresh ; Sorger, Gerhard
Publisher:	[S.l.] : SSRN
Subject:	Theorie \| Theory \| Ganzzahlige Optimierung \| Integer programming \| Mathematische Optimierung \| Mathematical programming