Discussion 12
1. The bin packing problem is as follows. You have an infinite supply of bins, each of which can hold M maximum weight. You also have n objects, each of which has a (possibly distinct) weight wi (any given wi is at most M). Our goal is to partition the objects into bins, such that no bin holds more than M total weight, and that we use as few bins as possible. This problem in general is NP-hard.
Give a 2-approximation to the bin packing problem. That is, give an algorithm that will compute a valid partitioning of objects into bins, such that no bin holds more than M weight, and our algorithm uses at most twice as many bins as the optimal solution. Prove that the approximation ratio of your algorithm is two.
2. Suppose you are given a set of positive integers A: a1 a2 … an and a positive integer B. A subset S ⊆ A is called feasible if the sum of the numbers in S does not exceed B.
The sum of the numbers in S will be called the total sum of S. You would like to select a feasible subset S of A whose total sum is as large as possible.
Example: If A = {8, 2, 4} and B = 11 then the optimal solution is the subset S = {8, 2}.
Give a linear-time algorithm for this problem that finds a feasible set S ⊆ A whose total sum is at
least half as large as the maximum total sum of any feasible set S’ ⊆ A. Prove that your algorithm achieves this guarantee.
You may assume that each ai < B.
3. A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.
● Material 1 has density 2 tons/cubic meter, maximum available amount 40 cubic meters, and revenue $1,000 per cubic meter.
● Material 2 has density 1 ton/cubic meter, maximum available amount 30 cubic meters, and revenue $1,200 per cubic meter.
● Material 3 has density 3 tons/cubic meter, maximum available amount 20 cubic meters, and revenue $12,000 per cubic meter.
Write a linear program that optimizes revenue within the constraints. You do not need to solve the linear program.
4. Recall the 0/1 knapsack problem:
Input: n items, where item i has profit pi and weight wi, and knapsack size is W.
Output: A subset of the items that maximizes profit such that the total weight of the set ≤ W.
You may also assume that all pi ≥ 0, and 0 < wi ≤ W.
We have created the following greedy approximation algorithm for 0/1 knapsack: Sort items according to decreasing pi/wi (breaking ties arbitrarily).
While we can add more items to the knapsack, pick items in this order.
Show that this approximation algorithm has no nonzero constant approximation ratio.
In other words, if the value of the optimal solution is P*, prove that there is no constant ρ (1 > ρ > 0), where we can guarantee our greedy algorithm to achieve an approximate solution with total profit ρ P*.