# Hardness and Approximability of Dimension Reduction on the Probability Simplex
## 4 Approximation  
Given \(p\in\mathcal{P}_{n}\) and \(m<n\), let \(OPT\) denote the optimal value of the optimization problem (2), that is  
\[OPT=\min_{q\in\mathcal{A}_{m}(p)}D(q\|p). \tag{22}\]  
In this section, we design a greedy algorithm to compute an aggregation \(\overline{q}\in\mathcal{A}_{m}(p)\) of \(p\) such that  
\[D(\overline{q}\|p)<OPT+1. \tag{23}\]  
The idea behind our algorithm is to see the problem of computing an aggregation \(q\in\mathcal{A}_{m}(p)\) as a bin packing problem with \"overstuffing\" (see [31] and references therein quoted), which is a bin packing where overfilling of bins is possible. In the classical bin packing problem, one is given a set of items, with their associated weights, and a set of bins with their associated capacities (usually, equal for all bins). The objective is to place all the items in the bins, trying to minimize a given cost function. In our case, we have \(n\) items (corresponding to the components of \(p\)) with weights \(p_{1},\ldots,p_{n}\), respectively, and \(m\) bins, corresponding to the components of \(lb(p)\) (as defined in (4)) with capacities \(lb(p)_{1},\ldots,lb(p)_{m}\). Our objective is to place all the \(n\) components of \(p\) into the \(m\) bins _without exceeding_ the capacity \(lb(p)_{j}\) of each bin \(j\), \(j=1,\ldots,m\), by more than \((\sum_{i=1}^{m}p_{i})lb(p)_{j}\). For such a purpose, the idea behind Algorithm 1 is quite straightforward. It behaves like a classical First-Fit bin packing: to place the \(i\)th item, it chooses the first bin \(j\) in which the item can be inserted without exceeding its capacity by more than \((\sum_{i=1}^{m}p_{i})lb(p)_{j}\). In the following, we will show that such a bin always exists and that fulfilling this objective is sufficient to ensure the approximation guarantee (23) we are seeking. ```
1. Compute \(lb(p)=(p_{1}/\sum_{j=1}^{m}p_{j},\ldots,p_{m}/\sum_{j=1}^{m}p_{j})\);

2. Let \(lb_{j}^{i}\) be the content of bin \(j\) after the first \(i\) components of \(p\) have been placed \((lb_{j}^{0}=0\) for each \(j\in\{1,\ldots,m\})\);

3. For \(i=0,\ldots,n-1\)

Let \(j\) be the smallest bin index for which holds that \(lb_{j}^{i}+p_{i+1}<(1+\sum_{j=1}^{m}p_{j})lb(p)_{j}\), place \(p_{i+1}\) into the \(j\)-th bin: \(lb_{j}^{i+1}=lb_{j}^{i}+p_{i+1}\), \(lb_{k}^{i+1}=lb_{k}^{i}\), for each \(k\
eq j\);

4. Output \(\overline{q}=(lb_{1}^{n},\ldots,lb_{m}^{n})\). ```  
**Algorithm 1**GreedyApprox  
The step 3 of GreedyApprox operates as in the classical First-Fit bin packing algorithm. Therefore, it can be implemented to run in \(O(n\log m)\) time, as discussed in [32]. In fact, each iteration of the loop in step 3 can be implemented in \(O(\log m)\)-time by using a balanced binary search tree with height \(O(\log m)\) that has a leaf for each bin and in which each node keeps track of the largest remaining capacity of all the bins in its subtree. Lemma 2: _GreedyApprox computes a valid aggregation \(\overline{q}\in\mathcal{A}_{m}(p)\) of \(p\in\mathcal{P}_{n}\). Moreover, it holds that_  
\[D(\overline{q}||lb(p))<\log\left(1+\sum_{j=1}^{m}p_{j}\right). \tag{24}\]  
Proof: We first prove that each component \(p_{i}\) of \(p\) is placed in some bin. This implies that \(\overline{q}\in\mathcal{A}_{m}(p)\). contradicting (25). Consequently, let \(k\) be the smallest integer for which the content of the \(k\)-th bin does not exceed its capacity, i.e., for which \(lb_{k}^{i}<lb(p)_{k}\). For such a bin \(k\), we obtain  
\[\left(1+\sum_{j=1}^{m}p_{j}\right)lb(p)_{k} =lb(p)_{k}+\left(\sum_{j=1}^{m}p_{j}\right)lb(p)_{k}\] \[=lb(p)_{k}+\left(\sum_{j=1}^{m}p_{j}\right)\frac{p_{k}}{\sum_{j=1 }^{m}p_{j}}\] \[=lb(p)_{k}+p_{k}\] \[>lb_{k}^{i}+p_{k} \text{(since $lb(p)_{k}>lb_{k}^{i}$)}\] \[\geq lb_{k}^{i}+p_{i+1} \text{(since $p_{k}\geq p_{i+1}$)}. \tag{26}\]  
Thus, from (26), one derives that the algorithm places \(p_{i+1}\) into the bin \(k\) without exceeding its capacity \(lb(p)_{k}\) by more than \((\sum_{j=1}^{m}p_{j})lb(p)_{k}\).