Advanced Algorithms Assignment 1

You can find the assignment description here.

Exercise 1.

Exercise 1.1

We can observe that the Load Balancing problem with unsplittable jobs (which we know is NP-complete) is a strictly special case of this extended problem.
For example, we can consider an instance of the extended problem where the set of splittable jobs is empty. In this scenario, the input consists solely of unsplittable jobs, that is the original Load Balancing problem. Any algorithm that can solve the extended problem must also be able to solve this specific instance. Since finding the optimal makespan for an instance with only unsplittable jobs is NP-complete, the general problem containing both types must be at least as hard. Therefore, extended Load Balancing is NP-hard.
Let's prove that the problem also belongs to the class NP. To show this, we frame it as a decision problem: given a time threshold $K$ , does a schedule exist such that $T \leq K$ ? A proposed solution (certificate) is the full assignment of unsplittable jobs and the "flow" allocation for splittable jobs.
We can also verify the makespan $T$ for each machine $i$ by computing its total load $T_{i}$ as the sum of unsplittable processing times and the allocated fractions of splittable jobs. Since all calculations (sums and checking $T \leq K$ ) can be performed in polynomial time relative to the number of jobs $n$ and machines $m$ , the extended Load Balancing problem is in NP.
Since the problem is both NP-hard and in NP, the extended Load Balancing problem is NP-complete.

Exercise 1.2

We can extend the smarter greedy algorithm that first sorts and re-indexes the jobs such that $t_{1} \geq \dots \geq t_{n}$ , and then applies the original greedy algorithm, to handle instances that may also contain splittable jobs.

First, we separate the jobs into unsplittable and splittable sets. Let the set of unsplittable jobs be $U$ with processing times ${t_{j}}_{j \in U}$ and the set of splittable jobs be $S$ with processing times ${s_{k}}_{k \in S}$ . We then order the unsplittable jobs in descending order ( $t_{1} \geq t_{2} \geq \dots \geq t_{| U |}$ ) and assign each job greedily to the machine $i$ with minimum current load $T_{i}$ , exactly as in the original algorithm.

Let $T_{i}^{unsplit}$ denote the load of machine $i$ after all unsplittable jobs, and let $T_{U} = max_{i} T_{i}^{unsplit}$ be the intermediate makespan.

Next, for the splittable jobs, we calculate the total splittable work $W_{S} = \sum_{k \in S} s_{k}$ . We then compute the total average load for the entire instance: $L_{a v g} = (\sum_{i} T_{i}^{unsplit} + W_{S}) / m$ . The splittable work is then used to "fill" any machine $i$ whose load $T_{i}^{unsplit}$ is less than $L_{a v g}$ , raising its load up to $L_{a v g}$ . If a machine $j$ already has $T_{j}^{unsplit} \geq L_{a v g}$ , it receives no splittable work.

The final makespan $T$ is therefore the maximum of the original highest unsplittable load and this average load.

T = max (T_{U}, L_{a v g})

Now we have to prove that $T \leq 1.5 T^{*}$ .

First, we know the guarantee for the unsplittable part: $T_{U} \leq 1.5 \cdot T_{U}^{*}$ , where $T_{U}^{*}$ is the optimal makespan for an instance with only the jobs in $U$ .

$T^{*} \geq T_{U}^{*}$ (since the optimum for the full problem cannot be better than the optimum for a sub-problem) and $T^{*} \geq L_{a v g}$ (since the optimum cannot be better than the perfect average).

We can simply check the two cases for our final makespan $T$ :

If $T = T_{U}$ the ratio holds, since the makespan is determined by an unsplittable load. We have $T = T_{U} \leq 1.5 T_{U}^{*} \leq 1.5 T^{*}$ .
If $T = L_{a v g}$ , the makespan is determined by the average load. We have $T = L_{a v g} \leq T^{*}$ . In this case, our solution is optimal.

In both cases the final makespan $T \leq 1.5 \cdot T^{*}$ , so the approximation ratio is maintained.

Exercise 2.

Exercise 2.1

We can observe that the function $f (x, y) = \sum_{i = 1}^{n} (| x - x_{i} | + | y - y_{i} |)$ is separable. We can rewrite the function by grouping the $x$ and $y$ terms independently:

f (x, y) = (\sum_{i = 1}^{n} w_{i} | x - x_{i} |) + (\sum_{i = 1}^{n} w_{i} | y - y_{i} |)

Let $f_{x} (x)$ denote the $x$ -dependent term and $f_{y} (y)$ denote the $y$ -dependent term. To minimize the total function $f (x, y) = f_{x} (x) + f_{y} (y)$ , we can find the coordinate $x^{*}$ that minimizes $f_{x} (x)$ and the coordinate $y^{*}$ that minimizes $f_{y} (y)$ completely separately. This reduces the 2D problem to two independent 1D problems, that are basically the weighted median problem.

We now describe the algorithm to find the optimal $x^{*}$ ; the algorithm for $y^{*}$ is identical. First, we calculate the total weight $W = \sum_{i = 1}^{n} w_{i}$ . We then create a list of pairs $(x_{i}, w_{i})$ and sort this list in non-decreasing order based on the $x_{i}$ coordinates.

Next, we iterate through this sorted list, maintaining a cumulative weight sum $S$ , initialized to zero. For each point $(x_{k}, w_{k})$ in the sorted list, we add its weight $S = S + w_{k}$ . The first coordinate $x_{k}$ for which this cumulative sum reaches or exceeds half the total weight (i.e., $S \geq W / 2$ ) is the weighted median. We set $x^{*} = x_{k}$ and terminate the 1D search. The final optimal point is $(x^{*}, y^{*})$ .

Correctness and time bound:
The correctness of separating the problem follows from the additive nature of the Manhattan distance.
The correctness of the algorithm relies on $f_{x} (x)$ being a convex function. Let's study the derivative to find the minimum.

We begin by expressing the derivative of the sum as the sum of the derivatives, noting that $\frac{d}{d x} | x - x_{i} | = sgn (x - x_{i})$ :

f_{x}^{'} (x) = \sum_{i = 1}^{n} w_{i} \cdot sgn (x - x_{i})

For any point $x$ not equal to any $x_{i}$ , the function is differentiable. We divide the sum into two groups:

Group 1 ( $x > x_{i}$ ): then $sgn (x - x_{i}) = + 1$ .
Group 2 ( $x < x_{i}$ ): then $sgn (x - x_{i}) = - 1$ .

Substituting the signs:

f_{x}^{'} (x) = \sum_{x_{i} < x} w_{i} \cdot (+ 1) + \sum_{x_{i} > x} w_{i} \cdot (- 1)

f_{x}^{'} (x) = \sum_{x_{i} < x} w_{i} - \sum_{x_{i} > x} w_{i}

The function $f_{x} (x)$ is minimized at the point $x^{*}$ where the difference is zero, meaning the total weight "pulling" to the left equals the total weight "pulling" to the right. This transition occurs precisely at the weighted median $x_{k}$ because, by definition, $x_{k}$ is the first point where the cumulative weight $S$ reaches $W / 2$ .

For the time bound, the algorithm is dominated by the sorting step. Let $n$ be the number of points. Calculating $W$ takes $O (n)$ time. Sorting the $n$ pairs takes $O (n \log n)$ time. The final pass to find the median takes $O (n)$ time. Since this procedure is run twice, the total time complexity is $O (n \log n) + O (n \log n) = O (n \log n)$ .

Actually, this bound can be improved to $O (n)$ using a Weighted Quickselect algorithm. To guarantee this linear performance and avoid the $O (n^{2})$ worst case, a non-unbalanced pivot is chosen in linear time using the Median of Medians algorithm as a pivot selection strategy. This reduces the total time complexity for the 2D problem to $O (n) + O (n) = O (n)$ , which is asymptotically optimal, although the two algorithms are not so easy to implement.

Exercise 2.2

Let:

$p = (x, y)$ be any point in the plane
$p_{i} = (x_{i}, y_{i})$ be the $i$ -th site
$f_{e} (p) = \sum_{i = 1}^{n} w_{i} \cdot \sqrt{(x - x_{i})^{2} + (y - y_{i})^{2}}$ the true Euclidean cost function
$f_{m} (p) = \sum_{i = 1}^{n} w_{i} \cdot (| x - x_{i} | + | y - y_{i} |)$ be the Manhattan cost function
$p_{e_{*}}$ be the point that truly minimizes the Euclidean cost $f_{e} (p)$
$p_{m_{*}}$ be the point found by our algorithm, which minimizes the Manhattan cost $f_{m} (p)$ .

Our goal is to prove that the Euclidean cost of our algorithm's solution is at most $\sqrt{2}$ times the Euclidean cost of the true optimal solution, that is, $f_{e} (p_{m_{*}}) \leq \sqrt{2} \cdot f_{e} (p_{e_{*}})$ .

We must use two fundamental geometric inequalities that relate the Euclidean distance ( $d_{e}$ ) and Manhattan distance ( $d_{m}$ ) between any two points:

$d_{e} \leq d_{m}$ , or $\sqrt{Δ x^{2} + Δ y^{2}} \leq Δ x + Δ y$
$d_{m} \leq \sqrt{2} \cdot d_{e}$ , or $Δ x + Δ y \leq \sqrt{2} \cdot \sqrt{Δ x^{2} + Δ y^{2}}$

By the definition of $f_{e}$ , we have $f_{e} (p_{m_{*}}) = \sum_{i = 1}^{n} w_{i} \cdot d_{e} (p_{m_{*}}, p_{i})$ . Applying inequality 1 ( $d_{e} \leq d_{m}$ ) to every term in the sum, this is less than or equal to $\sum_{i = 1}^{n} w_{i} \cdot d_{m} (p_{m_{*}}, p_{i})$ , which is precisely the definition of $f_{m} (p_{m_{*}})$ . This gives us $f_{e} (p_{m_{*}}) \leq f_{m} (p_{m_{*}})$ .

Next, we can use the key property of our algorithm, that is $p_{m_{*}}$ is the point that minimizes $f_{m}$ . Therefore, $f_{m} (p_{m_{*}})$ must be less than or equal to the Manhattan cost of any other point, including the true Euclidean optimal point $p_{e_{*}}$ . This is $f_{m} (p_{m_{*}}) \leq f_{m} (p_{e_{*}})$ .

Now, we apply inequality 2 ( $d_{m} \leq \sqrt{2} \cdot d_{e}$ ) to every term in the sum $f_{m} (p_{e_{*}}) = \sum_{i = 1}^{n} w_{i} \cdot d_{m} (p_{e_{*}}, p_{i})$ . This yields $\sum_{i = 1}^{n} w_{i} \cdot \sqrt{2} \cdot d_{e} (p_{e_{*}}, p_{i})$ . By factoring out the $\sqrt{2}$ constant, we get $\sqrt{2} \cdot \sum_{i = 1}^{n} w_{i} \cdot d_{e} (p_{e_{*}}, p_{i})$ , which is by definition equal to $\sqrt{2} \cdot f_{e} (p_{e_{*}})$ .