The Binary Merging Problem
Consider a ground set U of size m, and a collection of n sets, A := {A1,...,An } where each Ai ✓ U.
A merge schedule consists of two parts: (i) a full binary tree T := (V,E) with n labeled leaves; (ii) a
permutation ⇡ : [n] ! [n] which assigns every set APto the leaf number ⇡(i). A full binary tree is a i
binary tree in which every node has either 0 or 2 children. Given a set system (U,A), the cost of a merge schedule (T, ⇡) is defined as: cost(T, ⇡, A) = v2T|Av|, where Av is the union of all sets that are assigned to the leaves of the subtree rooted at the node v. The binary merging problem is to find a merge schedule (T, ⇡) with the minimum cost.
In other words, the full binary tree T defines a way to merge these sets, and finally, all sets are merged into one set. Each node in T corresponds to a “merge” operation, and it merges two sets, each of which is either a union of some initial sets or an initial set itself. The cost of this merge operation is the size of the set after merging these two sets. An example with input 5 sets: A1 = {1,2,3,5}, A2 = {1,2,3,4}, A3 = {3,4,5}, A4 = {6,7,8} and A5 = {7,8,9} is shown in Figure 1. Figure 1 is a solution that is returned by the following algorithm.
Algorithm. Consider an arbitrary order of the input sets. The algorithm runs in rounds, and in each
round, the algorithm aims to merge sets two-by-two. Consider an arbitrary iteration of the algorithm
and assume that the number of sets is n0 at the beginning of this iteration. Divide these n0 sets into
n0 pairs. If n0 is an odd number, leave alone an arbitrary set and group the other n0  1 sets into 2
n01 pairs. Merge each pair of sets and continue till there is only one set left. An example is shown in 2
Figure 1.
{1,2,3,4,5,6,7,8,9} 3
 2 {1,2,3,4,5,6,7,8} A5 {7,8,9}
  1 {1,2,3,4,5} 1 {3,4,5,6,7,8} A1 A2 A3 A4
{1,2,3,5} {1,2,3,4} {3,4,5} {6,7,8}
oo
Figure 1: The solution returned by the above algorithm. The label inside the leaf nodes denotes the corresponding set. The label inside internal nodes denotes the iteration in which the merge happened. The sets corresponding to each node are shown outside the node. The cost of this solution is 45.
1δ
f0 0
 o1 d 0
 
Q1. Prove that OPT >= i=1∑n |Ai|, where OPT is the cost of the optimal merge schedule.
Q2. Let T be the full binary tree produced by the above algorithm. What is the height of T? The
height of a binary tree is defined as the length of the longest path from the root to a leaf node. The length of a path is defined as the number of edges included in this path. For example, the height of the tree in Figure 1 is 3.
Q3. What is the approximation ratio of the above algorithm?
(Hint: the approximation ratio is related to the height of the produced full binary tree.)
Q4. Prove that the above analysis is tight. Namely, construct an instance I of the binary merging problem such that ALG(I ) / OPT(I) >= [log n] + 1, where OPT(I ) is the cost of the optimal solution to I and
 OPT(I )
ALG(I) is the cost of the solution by running the above algorithm.
Q5. Is it possible to design another algorithm running in polynomial time that achieves an approxi- mation ratio better than (dlog ne + 1)? If so, please design your algorithm and give the analysis; If not, please give the reason.