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 n and a positive integer B. A subset 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 whose total sum is at
least half as large as the maximum total sum of any feasible set S 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 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*.
A set of n space stations need your help in building a radar system to track spaceships traveling between them. The ith space station is located in 3D space at coordinates (xi, yi, zi). The space stations never move. Each space station i will have a radar with power ri, where ri is to be determined. You want to figure how powerful to make each space station’s radar transmitter, so that whenever any spaceship travels in a straight line from one space station to another, it will always be in radar range of either the first space station (its origin) or the second space station (its destination). A radar with power r is capable of tracking spaceships anywhere in the sphere with radius r centered at itself. Thus, a spaceship is within radar range through its trip from space station i to space station j if every point along the line from (xi, yi, zi) to (xj, yj, zj) falls within either the sphere of radius ri centered at (xi, yi, zi) or the sphere of radius rj centered at (xj, yj, zj). The cost of each radar transmitter is proportional to its power, and you want to minimize the total cost of all of the radar transmitters. You are given all of the (x1, y1, z1), … ,(xn, yn, zn) values, and your job is to choose values for r1,…,rn. Express this problem as a linear program.