Integer knapsacks and the Frobenius problem

Start: 04/21/2011 - 4:15pm
End  : 04/21/2011 - 5:15pm

Statistics/OR/Math Finance Seminar

Lenny Fukshansky, CMC


Given unlimited supply of N > 1 types of objects of respective integer weights a_1,...,a_N and corresponding integer prices p_1,...,p_N, the integer knapsack problem aims to maximize the value of a knapsack that can hold at most the weight W. This is an important problem in operations research, which often arises in resource allocation with financial constraints; it is known to be NP-complete. The integer knapsack problem is closely related to another famous NP-hard problem, the linear Diophantine Frobenius problem (FP): assuming that the weights a_1,...,a_N are relatively prime, find the largest weight that such a knapsack CANNOT have. I will discuss this connection, and will then talk about FP in more details, reviewing some of the recent results on this extensively studied problem.

Harvey Mudd College 3rd floor Sprague. Refreshments at 4pm.