## 2 Algorithm
### Description of Algorithm GS Modified
Thus later \(m^{\prime}\) proposed to \(w\) from \(L^{\prime}_{m^{\prime}}\). According to the algorithm, \(w\) would have accepted him and could not later on become matched to someone subsatellitic and equally good for her as \(m^{\prime}\). A contradiction. \(\Box\)  
**Theorem 1**. : _Algorithm GS Modified computes a stable matching \(M\) which is a \(\frac{3}{2}\)- approximation of the optimal solution. Algorithm GS Modified runs in \(O(m)\) time._  
**Proof. ** By Lemma 2, matching \(M\) computed by Algorithm GS Modified is stable and does not contain dangerous paths. Therefore \(M\) is a \(\frac{3}{2}\)-approximation of the optimal solution. The running time of the algorithm is proportional to the sum of the lengths of lists \(L_{m}\) and \(L^{\prime}_{m}\). By the length of list \(L_{m}\) or \(L^{\prime}_{m}\) we mean the number of people on it and not the number of ties. Each edge of \(L_{m}\) is scanned at most twice-twice only if the first time it was scanned, it was special, and each edge of \(L^{\prime}_{m}\) is scanned at most once. Checking whether a given woman \(w\) is co-satellitic or co-subsatellitic can be done in constant time as follows. Suppose that \(w\) is matched to man \(m\). We look at the tie at the top of list \(L_{m}\). If this tie contains woman \(w\) and some free woman \(w^{\prime}\), then \(w\) is co-satellitic, otherwise she is not. (Recall that the free women proceed matched ones in a tie.) To facilitate checking whether a given man is subsatellitic, each man has the counter of free women incident with him, and whenever a woman becomes matched and moves herself to the end of the ties, men decrease their respective counters. The number of movements in the ties is upperbounded by the sum of the lengths of lists \(L_{m}\) as once a woman becomes matched, she stays so. \(\Box\)Let us finally make the following remark. If we break ties and run the classic Gale-Shapley algorithm, then the cardinality of the computed matching depends on the order in which we break ties. Algorithm GS Modified outputs a matching that would have been output by the GS algorithm if ties were broken as follows. Men's lists would be identical to those at the beginning of Algorithm GS Modified but for one thing: if at some point during running Algorithm GS Modified, man \(m\) proposes to a co-satellitic woman \(w\), and as a result \(m\) gets matched to \(w\), and \(w\)'s partner \(M(w)\) gets matched to his satellite \(w^{\prime}\), then a tie on \(L_{M(w)}\) would be broken in such a way that \(w^{\prime}\) comes before \(w\). Every tie \(t\) on a woman \(w\)'s list would be first broken into \((m_{1},m_{2},\ldots,m_{s})\) in such a way that \(m_{1}\) denotes the first man of \(t\) to whom \(w\) got matched without becoming co-satellitic, and assuming that it happened at some step \(S\), \(m_{2}\) denotes the first man of \(t\) who proposed to \(w\) after step \(S\), \(m_{3}\) denotes the second man of \(t\), who proposed to \(w\) after step \(S\) and so on. Next we would make the following alterations on women's lists: if at some point, man \(m\) proposes from \(L^{\prime}_{m}\) to a co-subsatellitic woman \(w\) matched to \(M(w)\), then a tie on \(L_{w}\) would be broken in such a way that \(m\) comes before \(M(w)\).