Homework 2

Problem 1.

You have been appointed master of the newly built Gapcheon Port. When a ship arrives, with \(n\) containers of weight \(w_1, w_2, \ldots, w_n\), they need to be loaded onto trucks, each of which can carry \(K\) units of weight. (All numbers are integers.)

You can stack multiple containers in each truck as long as they don't exceed the maximum weight \(K\). Your goal is to minimize the number of trucks needed.

This problem is NP-complete (you can prove this for practice, if you like, but it's not part of the homework), so we will try an approximation algorithm. Here is a greedy algorithm: Start with an empty truck, and being piling containers \(1, 2, \dots\) into it until it would overflow. Send off this truck, then continue with a fresh truck.

  1. Give an example of a set of weights and a value \(K\) where this algorithm does not use the minimum possible number of trucks.
  2. Prove that this algorithm is a \(2\)-approximation algorithm, for any set of weights and any \(K\).

Problem 2.

Let \(G\) be a graph defined over \(n\) vertices, and let the vertices be ordered: \(v_1,\ldots, v_n\). Let \(G_i\) be the induced subgraph of \(G\) on \(v_1,\ldots, v_i\). Formally, \(G_i = (V_i, E_i)\), where \(V_i = \{v_1,\ldots, v_i\}\) and
\[ E_i = \bigg\{ u v \in E \mathop{\bigg|} u,v \in V_i \text{ and } u v \in E(G)\bigg\}. \]

The greedy coloring algorithm colors the vertices, one by one, in the given ordering. Let \(k_i\) denote the number of colors the algorithm uses to color the first \(i\) vertices.

In the \(i\)th iteration, the algorithm considers \(v_i\) in the graph \(G_i\). If all the neighbors of \(v_i\) in \(G_i\) are using all the \(k_{i-1}\) colors used to color \(G_{i-1}\), the algorithm introduces a new color (i.e., \(k_i=k_{i-1}+1\)) and assigns it to \(v_i\). Otherwise, it assign \(v_i\) one of the colors \(1, \ldots, k_{i-1}\) (i.e., \(k_i=k_{i-1}\)).

  1. Give an example of a graph \(G\) with \(n\) vertices, and an ordering of its vertices, such that even if \(G\) can be colored using a constant number of colors, the greedy algorithm would color it with \(\Omega(n)\) colors.
  2. Assume now that \(G\) is a planar graph, and choose the ordering carefully as follows: \(v_n\) is chosen as a vertex of smallest degree in \(G = G_n\), then \(v_{n-1}\) is chosen as a vertex of smallest degree in \(G_{n-1}\), etc. In each step, we choose \(v_i\) as a vertex of smallest degree in \(G_i\). Prove that for a planar graph with this ordering, the greedy coloring algorithm will find a coloring with at most six colors. (Hint: A planar graph with \(n\) vertices has at most \(3n-6\) edges. You can use this fact without proving it.)

Problem 3.

Let \(R\) be a set of squares (for instance, a \(0.5 \times 0.5\) square, a \(0.4 \times 0.4\) square, and a \(0.6 \times 0.6\) square).

Your goal is to pack some of these squares inside the unit square (that is, the \(1 \times 1\) square) to cover as much of the area of the unit square as possible. Packing means that the squares are allowed to touch, but they cannot overlap (their interior has to be disjoint).

Give a polynomial time algorithm that outputs a packing that covers at least \(\mathrm{OPT}/4\) area of the unit square, where \(\mathrm{OPT}\) is the area of the unit square covered by the optimal solution.

Problem 4.

You are helping a company where clients bring in jobs each day for processing. Each job has a processing time \(t_{i}\) that is known when the job arrives. The company has 10 machines, and each job can be processed on any of these ten machines.

The company is currently running the greedy-balance algorithm we discussed in the class: Each job is immediately assigned to the machine which currently has the smallest load.

However, the company has recently heard that this algorithm can produce solutions with makespan as much as twice the minimum possible, and so they are worried. However, their experience is quite good: In the last month, they never encountered a makespan more than 20% above the average load, that is \(\frac{1}{10}\sum_{i} t_{i}\).

To try to understand this, you ask a bit about the jobs and loads they see: The size of their jobs ranges between \(1\) and \(50\), that is \(1 \leq t_{i} \leq 50\) for all \(i\), and the total load is quite high, at least \(\sum_{i} t_{i}\geq 3000\) every day.

Prove that under these conditions the greedy-balance algorithm never does worse than 20% above the optimum, in other words, it is a \(1.2\)-approximation.