Homework 8

CS 482 - Spring 2005

Due: Friday, Apr 22

Note: Include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.

Part A

1. Problem 3 at the end of Chapter 10. (Hint: Think about Dynamic Programming.)

   Suppose we are given a directed graph G = (V,E), with V = {v₁, v₂, ..., v_n}, and we want to decide whether G has a Hamiltonian path from v₁ to v_n. (That is, is there a path in G that goes from v₁ to v_n, passing through every other vertex exactly once?)

   Since the Hamiltonian path problem is NP-complete, we do not expect that there is a polynomial-time solution for this problem. However, this does not mean that all non-polynomial-time algorithms are equally "bad." For example, here's the simplest brute-force approach: for each permutation of the vertices, see if it forms a Hamiltonian path from v₁ to v_n. This takes time roughly proportional to n!, which is about 3 times 10¹⁷ when n = 20.

   Show that the Hamiltonian path problem can in fact be solved in time O(2ⁿ p(n)), where p(n) is a polynomial function of n. This is a much better algorithm for moderate values of n; 2ⁿ is only about a million when n = 20.

Part B

2. Problem 1 at the end of Chapter 11.

   Suppose you're acting as a consultant for the Port Authority of a small Pacific Rim nation. They're currently doing a multi-billion dollar business per year, and their revenue is constrained almost entirely by the rate at which they can unload ships that arrive in the port.

   Here's a basic sort of problem they face. A ship arrives, with n containers of weight w₁, w₂, ..., w_n. Standing on the dock is a set of trucks, each of which can hold K units of weight. (You can assume that K and each w_i is an integer.) You can stack multiple containers in each truck, subject to the weight restriction of K; the goal is to minimize the number of trucks that are needed in order to carry all the containers. This problem is NP-complete (you don't have to prove this).

   A greedy algorithm you might use for this is the following. Start with an empty truck, and begin piling containers 1, 2, 3, ... into it until you get to a container that would overflow the weight limit. Now declare this truck "loaded" and send it off; then continue the process with a fresh truck.

   1. Give an example of a set of weights, and a value of K, where this algorithm does not use the minimum possible number of trucks.
   2. Show that the number of trucks used by this algorithm is within a factor of 2 of the minimum possible number, for any set of weights and any value of K.

Part C

3. Problem 5 at the end of Chapter 11. (Remember that you need to prove your approximation bound.)

   Recall that in the basic load balancing problem from lecture, we're interested in placing jobs on machines so as to minimize the makespan --- the maximum load on any one machine. In a number of applications, it is natural to consider cases in which you have access to machines with different amounts of processing power, so that a given job may complete more quickly on one of your machines than on another. The question then becomes: how should you allocate jobs to machines in these more heterogeneous systems?

   Here's a basic model that exposes these issues. Suppose you have a system that consists of m slow machines and k fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now, you're given a set of n jobs; job i takes time t_i to process on a slow machine and time t_i / 2 to process on a fast machine. You want to assign each job to a machine; as before, the goal is to minimize the makespan --- i.e. the maximum, over all machines, of the total processing time of jobs assigned to that machine.

   Give a polynomial-time algorithm that produces an assignment of jobs to machines with a makespan that is at most three times the optimum.