CSci 3501 Algorithms and Computability - Lab 4.

September 14. Due Wednesday, September 20 at 11:59pm

What to submit and when:

Lab assignment

Work in pairs; work with a different partner than last time

30 points. Grading criteria:

Lab overview and goals

The goal of the lab is develop and implement an approximation algorithm to solve a Bin Packing Problem: find a way to pack N items of different fixed sizes into 3 bins with capacity B each. The algorithm should try to minimize the amount of unused bin space (or, equivalently, the total unpacked amount).

Example: given B=20 and items of sizes

12, 4, 8, 15, 9, 3, 1, 10

you can pack the bins as [12, 8], [1, 4, 15], and [9, 10], with the leftover item of size 3.

It is proven that to find the optimal solution, one needs to consider all possibilities of packing which is exponential in N. However, there are good approximation algorithms that find a solution close to optimal in times polynomial in N. Your goal is to develop such an approximation algorithm, implement it, test it, and analyze its efficiency.

Specific requirements

What to submit

CSci 3501 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.