## 5 Distributed Algorithms for the Many-to-Many Maximum Weighted Matching Problem
### Approximation Ratio for the Distributed Algorithms  
Following the methodology in [8], in order to further analyze the distributed algorithm in both variations, we present a centralized algorithm for many-to-many maximum weighted matchings, for which we show that it behaves in the same way with the distributed algorithm and both have the same approximation ratio of \(\frac{1}{2}\). ```
\(M\leftarrow\emptyset;P\gets E\)forall the\(v\in V\)do\(counter(v)\gets d_{v}\)while\(P\
eq\emptyset\)do take a locally heaviest edge\((a,b)\in P\)\(M\gets M\cup(a,b)\)\(P\gets P\backslash(a,b)\)\(counter(a)\gets counter(a)-1\)\(counter(b)\gets counter(b)-1\)if\(counter(a)=0\)then\(P\gets P\backslash\left\{(a,n_{a})\mid n_{a}\in\Gamma_{a}\right\}\)if\(counter(b)=0\)then\(P\gets P\backslash\left\{(b,n_{b})\mid n_{b}\in\Gamma_{b}\right\}\)
```  
**Algorithm 3** LIC: Local Information-based Centralized algorithm for many-to-many maximum weighted matchings  
Algorithm LIC is a simple greedy algorithm with the distinctive feature of using only locally available information, by selecting locally heaviest edges in a centralized way. Note that the comment of Section 5 about the recursive nature of the locally heaviest edges is still valid here: by systematically removing from the edge pool \(P\) the edges we select (line 6, Algorithm 3), along with any unselected edges of nodes with filled quotas (lines 8 and 9, Algorithm 3), we get the same dynamics as in the distributed case (_cf._ Lemma 11). In the following theorem, using a similar proof strategy to the one used by [PERSON] [9] for his centralized one-to-one weighted matching algorithm, we prove that it achieves a \(\frac{1}{2}\)-approximation compared to the optimum algorithm (OPT) that selects edges with maximum weights over the whole graph. **Theorem 2**: _The LIC algorithm produces a many-to-many maximum weighted matching \(M_{C}\) that is a \(\frac{1}{2}\)-approximation of the matching \(M_{OPT}\) produced by the optimal algorithm, OPT._  
**Proof:** Let \(V_{C}\) be the set of nodes matched at least once by the LIC algorithm. We will show that the condition:  
\[w\left(M_{C}\right)\geq\frac{1}{2}w\left(\{(u,v)\in M_{OPT}|u\in V_{C}\lor v\in V _{C}\}\right) \tag{33}\]  
holds for every step of the LIC algorithm, that is, the weight of matching \(M_{C}\), \(w(M_{C})\), is at least \(\frac{1}{2}\) of the weight \(w(M_{OPT})\) of the optimal matching \(M_{OPT}\) when including only edges adjacent to nodes matched by LIC. Note that the algorithm can leave two or more nodes (completely) unmatched, but only if they are not connected in \(G(V,E)\) (if they are connected, they will be matched, since the possibility exists and they have available connection quotas, leaving possibly one odd node unmatched). By the time LIC terminates, for every \((u,v)\in E\), it would be either \(u\in V_{C}\) or \(v\in V_{C}\), and Equation (33) will become \(w\left(M_{C}\right)\geq\frac{1}{2}w\left(M_{OPT}\right)\). For the initial condition \(M_{C}=\emptyset\) Equation (33) holds. Let us assume that at some step of LIC, edge \((a,b)\) is included in the matching \(M_{C}\) and the left-hand side of Equation (33) increases by \(w(a,b)\). For the right-hand side, there are only two options: either \((a,b)\) is part of the optimal matching, \(M_{OPT}\), or two other edges, \((a,c)\) and \((b,d)\), occupy the respective slots of nodes \(a\) and \(b\) in the optimal matching. For these cases, we have the following:  
* \((a,b)\in M_{OPT}\): The total weight of the right-hand side is increased by \(\frac{1}{2}w(a,b)\) and Equation (33) holds. * \((a,c),\ (b,d)\in M_{OPT}:\) If both \(c,d\in V_{C}\), then both edges are already taken into account in the right-hand side's weight sum, and Equation (33) holds. If one or both \(c\) and \(d\) are not included in \(V_{C}\), then the total weight of the right-hand side is increased by \(\frac{1}{2}w(a,c)\), \(\frac{1}{2}w(b,d)\) or \(\frac{1}{2}\left(w(a,c)+w(b,d)\right)\) by the addition of \((a,c)\),\((b,d)\) or both, respectively.