# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
Since maximal strings from \(Y^{+}\) are chosen at most \(\mathsf{level}_{i}(Y)\) many timesup to round \(i\), it follows that the number of rounds where a nonunary, maximal string of the form \(vY\) for some \(v\) is selected is at most \((\mathsf{level}_{i}(Y)+1)^{2}\). Furthermore, the maximal increase \(\max\{s(j+1)-s(j)\mid j\in[0,i-1]\}\) in a single round is at most \(\mathsf{level}_{i}(Y)+1\), because the new nonunary nonterminal occurs in \(\mathbb{A}_{j+1}\) on at most \(\#_{j}(Y)\leq\mathsf{level}_{j}(Y)+1\leq\mathsf{level}_{i}(Y)+1\) many right-hand sides of rules for any \(j\leq i\) and the total number of occurrences of all other (nonunary) nonterminals does not increase (Lemma 7, point (1)). We conclude that for each unary nonterminal \(Y\), at most  
\[M=\{Y\in N_{i}\mid(Y\to v)\in P_{i}\text{ and }\gamma\text{ is a factor of }v\}\subseteq N_{i}\]6  
many rules are introduced such that the nonunary, maximal string \(\gamma\) satisfies \(\gamma=Yv\) or \(\gamma=vY\) for some \(v\) and each of those rules increases the total size that nonunary nonterminals contribute by at most \(\mathsf{level}_{i}(Y)+1\). In all other cases, we showed that the size that nonunary nonterminals contribute does not increase. Now we are able the prove Proposition 1. Proof of Proposition 1.: Let \(\mathbb{A}_{f}=\mathsf{Greedy}(X_{0}^{n})\) be the final SLP obtained by Greedy, i.e., after \(f\) rounds the algorithm stops because \(\mathbb{A}_{f}\) has no maximal string. First, we want to bound the level of unary nonterminals occurring in \(\mathbb{A}_{f}\). Assume there is a unary nonterminal \(X\) such that \(\mathsf{level}_{i}(X)=\lceil\log\log n\rceil\) after some round \(i\leq f\) of the algorithm. By Corollary 2, we have  
\[M=\{Y\in N_{i}\mid(Y\to v)\in P_{i}\text{ and }\gamma\text{ is a factor of }v\}\subseteq N_{i}\]7  
Consider the unique leaf node \(v_{X}\) in the tree \(T_{i}\) which has level \(\lceil\log\log n\rceil\) and label \((X,k)\) for some \(k\). If in some round \(j\in[i+1,f]\) two children with labels \((X,k+1)\) and \((Y,k)\) are attached to \(v_{X}\), i.e., the introduced rule in round \(j\) is \(Y\to X^{d}\) for some \(d\geq 2\), then we have \(t_{j}(X)+t_{j}(Y)\leq t_{j-1}(X)\leq t_{i}(X)\) by Lemma 7. To be more specific, if the length of the chosen maximal string \(X^{d}\) is exactly \(d=2\) and this maximal string \(XX\) occurs exactly twice without overlap in \(\mathbb{A}_{j-1}\), then we have \(t_{j}(X)+t_{j}(Y)=t_{j-1}(X)\) (and \(|\mathbb{A}_{j}|=|\mathbb{A}_{j-1}|\)). Please note that in this case, there does not exist a maximal string \(X^{d}\) or \(Y^{d}\) of \(\mathbb{A}_{k}\) for all \(k\in[j,f]\) (since \(Y\) occurs only twice and \(XX\) does not occur on right-hand sides of \(\mathbb{A}_{j}\)), i.e., the children of the node \(v_{X}\) in \(T_{k}\) are leaves for \(k\in[j,f]\). Otherwise, if the maximal string has length \(d\geq 3\) or occurs at least three times without overlap, then we have \(t_{j}(X)+t_{j}(Y)<t_{j-1}(X)\) since \(|\mathbb{A}_{j}|<|\mathbb{A}_{j-1}|\) holds in this setting. This means that when a new branch occurs in the tree \(T_{j}\) for some \(j\), then the new children of the branching node are either leaves of the final tree \(T_{f}\) or the corresponding nonterminals contribute strictly less to the size of the current SLP than the nonterminal which corresponds to the parent node did before the branch. We can iterate this argument for the children of the children of \(v_{X}\) and so on, i.e., if we consider the subtree rooted at \(v_{X}\) in \(T_{f}\), then from level to level the size that the nonterminals contribute decreases until only leaves occur at some level.