Problem: Suppose you are given a set of boxes, each specified by their height, width and depth in centimeters. All three side lengths of every box is strictly between 10 cm and 20 cm. As you should expect, one box can be placed in another if the first box can be rotated so that its height, width, and depth are respectively smaller than the height, width, and depth of the second box. Boxes can be nested recursively. We call a box visible if it is not inside another box.
Design an algorithm to nest the boxes so that the number of visible boxes is as small as possible.
Your answer must contain the following parts specified explicitly.
• Explain how you formulate the problem into a flow-network problem. Meaning how you construct a flow network with capacities of edges and the specified vertices s and t.
• Explain by justification why “the maximum flow value” or “minimum cut size” should correspond to the actual answer to the problem.
• How much time does the construction of flow network take, and how much time does the Ford Fulkerson’s Algorithm take when the Ford-Fulkerson’s algorithm runs in time O(value(flow)(|V| + |E|)-time.
1
