Design and Analysis of Algorithms
510.6401 Design and Analysis of Algorithms
January 21, 2008
Problem Set 1
Due: February 4, 2008. 1. In the bin packing problem, the input consists of a sequence of items I = {1, . . . , n} where each item i has a size, which is a real number 0 ≤ ai ≤ 1. The goal is to “pack” the items in the smallest possible number of bins of unit size. Formally, the items should be partitioned in disjoint subsets (bins), such that the total size in each bin is at most 1. The first fit heuristic scans the items one by one, and each item is assigned to the first bin that it can fit in. Prove that first-fit is a 2-approximation algorithm for bin packing. Hint. Bound from below the number of bins used by an optimal solution; and bound from above the number of bins used by first fit, using the observation that nearly all bins are at least half-full. 2. Suppose now that you want to pack as much as possible in a single bin. Formally, the input consists of a set of items I = {1, . . . , n}, where each item i has a size 0 < ai ≤ 1. A solution is a set of items S ⊂ I such that i∈S ai ≤ 1 (i.e., the size of the bag is 1). The value of a solution S is the total size of the items in the solution, i.e., i∈S ai . (a) Describe an optimal solution to the problem. What is the time complexity of your algorithm? (b) Give a polynomial-time algorithm with approximation ratio 2 (i.e., it guarantees that you fill at least half of the optimal value). What is the time complexity of your algorithm? Warning. The simplest solution doesn’t work! 3. Consider the following algorithm for the m-machine load-balancing problem (S is the set of jobs): Repeat: (a) Let A be the sum of weights of all jobs in S (b) Find a subset S1 ⊆ S whose sum of weights is close to A/m (c) S ← S \ S1 ; m ← m − 1 until m = 0. Suppose that the subset sum step above is implemented using an approximation algorithm, which guarantees that its result is within a factor of 1 − ǫ from the optimal subset sum, for some 0 < ǫ < 1. What can you say
January 21, 2008
Problem Set 1
Due: February 4, 2008. 1. In the bin packing problem, the input consists of a sequence of items I = {1, . . . , n} where each item i has a size, which is a real number 0 ≤ ai ≤ 1. The goal is to “pack” the items in the smallest possible number of bins of unit size. Formally, the items should be partitioned in disjoint subsets (bins), such that the total size in each bin is at most 1. The first fit heuristic scans the items one by one, and each item is assigned to the first bin that it can fit in. Prove that first-fit is a 2-approximation algorithm for bin packing. Hint. Bound from below the number of bins used by an optimal solution; and bound from above the number of bins used by first fit, using the observation that nearly all bins are at least half-full. 2. Suppose now that you want to pack as much as possible in a single bin. Formally, the input consists of a set of items I = {1, . . . , n}, where each item i has a size 0 < ai ≤ 1. A solution is a set of items S ⊂ I such that i∈S ai ≤ 1 (i.e., the size of the bag is 1). The value of a solution S is the total size of the items in the solution, i.e., i∈S ai . (a) Describe an optimal solution to the problem. What is the time complexity of your algorithm? (b) Give a polynomial-time algorithm with approximation ratio 2 (i.e., it guarantees that you fill at least half of the optimal value). What is the time complexity of your algorithm? Warning. The simplest solution doesn’t work! 3. Consider the following algorithm for the m-machine load-balancing problem (S is the set of jobs): Repeat: (a) Let A be the sum of weights of all jobs in S (b) Find a subset S1 ⊆ S whose sum of weights is close to A/m (c) S ← S \ S1 ; m ← m − 1 until m = 0. Suppose that the subset sum step above is implemented using an approximation algorithm, which guarantees that its result is within a factor of 1 − ǫ from the optimal subset sum, for some 0 < ǫ < 1. What can you say