Saturday, June 11, 2016

Coursera Approximation Algorithms Part I - Peer Assignment 3

Problem:



Solution:

(1) is pretty easy, it is obvious that we can have at most 5 items of size 6, and at most 3 items of size 10, so a simple addition table would show what the configurations are

0
10
20
30
0
0
10
20
30
6
6
16
26
36
12
12
22
32
42
18
18
28
38
48
24
24
34
44
54
30
30
40
50
60

So there are 13 configurations.

(2) The linear program is

Minimize $ \sum{x_c} $
Subject to $ \sum{x_c a_{s,c}} \ge n_s $

To see if a given solution is feasible for the linear program, we simply check. First, recall $ a_{s,c} $ is the number of items of size $ s $ in configuration $ c $, so we have:

$ a_{6,1} = 5 $
$ a_{10,1} = 0 $
$ a_{6,2} = 0 $
$ a_{10,2} = 3 $

And also $ n_s $ is the number of items of size $ s $, so

$ n_{6} = 14 $
$ n_{10} = 8 $

The constraints are now

$ x_{c_1} a_{6,1} + x_{c_2} a_{6,2} \ge n_{6} $
$ x_{c_1} a_{10,1} + x_{c_2} a_{10,2} \ge n_{10} $

Putting in the values, now we get

$ \frac{14}{5} 5 + \frac{8}{3} 0 \ge 14 $
$ \frac{14}{5} 0 + \frac{8}{3} 3 \ge 8 $

Now it is obvious the given solution is feasible!

(3) The solution is sparse, as we have only two non-zero entries.

(4) Following the given algorithm, we would round down the given $ x_c $ values, so we have

$ \lfloor x_{c_1} \rfloor  = \lfloor \frac{14}{5} \rfloor = 2 $ bins in configuration 1 and
$ \lfloor x_{c_2} \rfloor  = \lfloor \frac{8}{3} \rfloor = 2 $ bins in configuration 2.

(5) With the solution above, we have covered

$ 2 \times 5 = 10 $ items of size $ 6 $
$ 2 \times 3 = 6 $ items of size $ 10 $

So we have $ 14 - 10 = 4 $ items of size $ 6 $ and $ 8 - 6 = 2 $ items of size $ 10 $ to go in the problem $ \bar I $.

(6) For $ P_1 $, we will be opening two more bins, one for each configuration.

(7) Now we run next fit as follow

[6,6,6,6] [10,10]

So we also open two bins with next fit, so again, we are using two more bins.

(8) The total size is $ 6 \times 14 + 8 \times 10 = 164 $, we will need at least $ \lceil \frac{164}{30} \rceil = 6 $ bins. The solution above use 4 bins in the linear programming solution and 2 more bins with the rest using either method, so it is using 6 bins. As there is no way we can do any better than 6 bins, so the solution is optimal.

No comments :

Post a Comment