Integer Knapsacks and the Frobenius Problem
Document Type
Lecture
Department
Mathematics (CMC)
Publication Date
4-21-2011
Abstract
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.
Rights Information
© 2011 Lenny Fukshansky
Terms of Use & License Information
Recommended Citation
Fukshansky, Lenny. "Integer Knapsacks and the Frobenius Problem." Statistics/Operations Research/Math Finance seminar, Claremont Colleges, Claremont, California. 21 April 2011
Comments
This lecture was given during the Statistics/Operations Research/Math Finance seminar at the Claremont Colleges in April 2011.