Problem 6 Answer: "Taking Inventory"

Problem 6.1.

To reduce BIGP to IGP, take each object, as well as the entire grid, and increase its length and width by 1 each. For example, if the BIGP problem had an 8x10 grid, and y one 4x6 object, three 3x3 objects, and five 2x1 objects, the corresponding IGP problem has a 9x11 grid, with one 5x7 object, three 4x4 objects, and five 3x2 objects. If there is a solution to the BIGP problem, then the corresponding solution to the IGP problem can be gotten by extending each object one square right and down - this is always possible because of the buffer. To get from the solution to the IGP problem to the solution to the BIGP problem just go the other way. The image gives an example.

To reduce IGP to BIGP, just reverse the process - decrease each object's length and width by 1
each, and also decrease the grid's length and width by 1 each. However this runs into a problem because it's possible that some of the objects have a length or width of 1, and thus can't be decreased farther. If this is the case then first double the dimensions of all the objects in the IGP problem - this won't change the solution.

Problem 6.2.

Given an instance of the bin-packing problem with N bins of capacity V and a set of objects of size S1, S2, S3, etc., create an instance of IGP with an NxV grid and objects of size 1xS1, 1xS2, 1xS3, etc. Then a solution to the IGP instance can be converted into a solution to the bin-packing problem by putting each object into the bin corresponding to the row that the object was put in in the IGP solution, and of course if there is a solution to the bin packing problem it can be converted into a solution to the IGP instance by reversing the process. So the IGP instance has a solution if and only if the bin packing instance has a solution, so the reduction works.