A large class of optimization problems, called NP-complete problems, are likely to be intractable. Due to the great difficulty of finding the optimum solutions of these problems, researchers are turning towards the (maybe more significant) search of an approximation solution in the "average" case of a suitable stochastic model. A typical NP-complete problem is the Bin-Packing problem, which requires finding the minimum number of unit size bins needed to pack a given collection of items of size less than or equal to 1. In the most natural model of stochastic bin packing, sizes of items are distributed independently according to a given distribution u. (No special assumptions are made on u). Abstract mathematical tools have been used to obtain with relative ease rather unexpected results about optimal packing in this model. This project will investigate the bin packing problem, and its variations such as dual bin packing and strip packing, a stochastic version of the traveling salesman problem.
