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.