#### Title

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.