Abstract. The knapsack problem is an important combinatorial optimization problem that models binary and discrete decisions given limited resources. This talk addresses theoretical, and algorithmic issues regarding several knapsack problem variations, with application to homeland security. This talk presents dynamic programming algorithms that produce optimal solutions in pseudo-polynomial time, greedy heuristics, and fully polynomial time approximation schemes. The number of feasible solutions to the knapsack problem is discussed. In addition, an aviation security application is discussed in detail.
Knapsack Problem Variations and Homeland Security: Theory and Application