## 4 Approximating B-Matchings with Weighted Matchings
### Discarding the A Posteriori Term  
As the first step to approximate the maximizing satisfaction b-matching problem, we define a modified problem based on the same basic b-matching problem, but computing satisfaction using a modified version of Equation (4) (and subsequently Equation (1)):  
\[\Delta\overline{S}_{i}^{j} = S_{i,j}^{s}=\frac{1}{b_{i}}-\frac{R_{i}\left(j\right)}{b_{i}L_{ i}}, \tag{6}\] \[\overline{S}_{i} = S_{i}^{s}=\frac{c_{i}}{b_{i}}-\frac{\sum\limits_{j\in C_{i}}R_{i }\left(j\right)}{b_{i}L_{i}},c_{i}\leq b_{i} \tag{7}\]  
Using the above definition, we effectively disregard the dynamic part of Equation (4), making the prospective satisfaction increase \(\Delta S_{i}^{j}\) of node \(i\) independent of the number of connections. We refer to the node satisfaction defined by Equation (7) as _truncated satisfaction_ and the corresponding maximizing satisfaction b-matching problem as a _truncatedS maximizing satisfaction b-matching problem_. In the following lemma, we prove that by solving the truncatedS maximizing satisfaction b-matching problem, we get an approximation of the original problem. **Lemma 1**: _The truncatedS maximizing satisfaction b-matching problem is a \(\frac{1}{2}\left(1+b_{\max}^{-1}\left(1+\frac{1-b_{\max}^{-1}}{2s+b_{\max}^{- 1}}\right)\right)\)-approximation of the maximizing satisfaction b-matching problem, where \(b_{\max}\) is the maximum connection quota in the graph and \(s=\frac{L_{\max}}{L_{\min}}\) is the ratio of the maximum and minimum neighbor list sizes in the graph, \(L_{\max}\) and \(L_{\min}\), respectively._  
**Proof:** Since only \(S_{i}^{s}\) is used in the modified maximizing satisfaction b-matching problem, we are interested in studying the ratio:  
\[r_{i}=\frac{S_{i}^{s}}{S_{i}^{s}+S_{i}^{d}} \tag{8}\]  
and, specifically, its minimum value, \(r_{\min}\). Knowing this minimum value, we can conclude that the total satisfaction of the modified problem, \(S_{mod}\), is a \(r_{\min}\)-approximation of the total satisfaction of original b-matching problem \(S_{orig}\), since:  
\[S_{mod}=\sum_{i=1}^{n}S_{i}^{s}=\sum_{i=1}^{n}r_{i}\left(S_{i}^{s}+S_{i}^{d} \right)\geq r_{\min}\sum_{i=1}^{n}\left(S_{i}^{s}+S_{i}^{d}\right)=r_{\min}S _{orig} \tag{9}\]where \(n=|V|\) is the number of nodes in the graph. Note that we are looking for the minimum value \(r_{\rm min}\), and therefore, we can assume that a given node \(i\) has connected with the desired amount of neighbors \(b_{i}\) since then the difference between \(S_{i}^{s}\) and \(S_{i}^{d}\) is maximized, as we show below. Initially, consider the scenario in which every node \(i\) is connected with its bottom-most \(b_{i}\) neighbors. It is easy to see that \(S_{i}^{d}\) gets its maximum value when the length of the list is maximized (\(|C_{i}|=b_{i}\)), since the dynamic part of the satisfaction increase \(\Delta S_{i}^{j}\) is due to the connection list \(C_{i}\) of node \(i\). In this case of \(|C_{i}|=b_{i}\) connections, \(S_{i}^{s}\) achieves its minimum value when the connections \(j\in C_{i}\) are drawn from the bottom of the preference list \(L_{i}\). Since both of these conditions are met in the scenario considered here, the relative value of \(S_{i}^{d}\) is maximized or, equivalently, the relative value of \(S_{i}^{s}\) is minimized and the sums of dynamic and static parts, \(S_{i}^{d}\) and \(S_{i}^{s}\), acquire the values of \(s_{i}^{d}\) and \(s_{i}^{s}\), respectively.