## 4 Implementation and Running Time
And every man \(m\) subscribe each quadruplet \((m,w,j,0)\) to the central authority, where \(j\) is the index of woman \(w\) in \(m\)'s list. The central authority sorts these quadruplets and fuses neighboring pairs getting a list of quadruplets \((m,w,j,i)\), and stores \(I_{m}(j)=i\). After these detailed descriptions it is obvious that both the local and the global algorithms run in linear time. **5. Generalizations to the Hospitals/Residents Problem**It is well-known that algorithms for the one-to-one model can be easily converted to corresponding algorithms (for example, by cloning) for the many-to-one problems (see e.g., [15]). We detail the many-to-one case, because of the great importance and many practical usage of this model. In the _Hospitals/Residents_ problem, (also called Colleges/Students problem, and by many other names) the roles of women are played by hospitals and the roles of men are played by residents. Moreover, each hospital \(w\) has a positive integer capacity \(c(w)\), the number of free positions. Instead of matchings, we consider _assignments_, that is a subgraph \(F\) of \(G\), such that all residents have degree at most one in \(F\), and each hospital \(w\) has degree at most \(c(w)\) in \(F\). For a resident \(m\) who is assigned, \(F(m)\) denotes the corresponding hospital. For a hospital \(w\), \(F(w)\) denotes the set of residents assigned to it. We say that hospital \(w\) is _full_ if \(|F(w)|=c(w)\), and otherwise _under-subscribed_. Here a pair \(mw\) is _blocking_, if \(mw\in E\setminus F\) (they are an acceptable pair and they are not assigned to each other) and  
* \(m\) is either unassigned or \(\mathrm{pri}(m,w)>\mathrm{pri}(m,F(m))\), and
* \(w\) is either under-subscribed or \(\mathrm{pri}(w,m)>\mathrm{pri}(w,m^{\prime})\) for at least one resident \(m^{\prime}\in F(w)\). An assignment is _stable_ if there is no blocking pair. First, we consider the case when ties can only reside on hospitals lists. In [4, 14, 15] it was shown that if the preference lists of residents are strictly ordered, then an easy modification of GSA1 (called HRGSA1) gives a \(3/2\)-approximation in linear time. If we consider the resident-proposal version of the new algorithm, we can observe that as there are no ties on the resident's side, no uncertain resident exists, consequently the new algorithm runs equivalently to HRGSA1. This algorithm is the same as that of [PERSON] and [PERSON] with only one modification: if a resident is rejected by all hospitals for the first time, he/she gets an extra score of a half point (raising the priority by one half at every hospital; the same effect as when a man becomes a bachelor), the list is recovered, reactivates himself/herself and starts making applications from the beginning of his/her list. However, the new algorithm makes it possible to run the hospital-proposal version as well. It will also give now a \(3/2\) approximation, and expectedly it results in a stable assignment that is better for the hospitals than the result of the resident-proposal scheme. This statement should be tested by some empirical future work. From now on we change the roles: _hospitals play the role of men_ (as they will propose), and _residents play the role of women_. For avoiding any confusion, from this point hospitals will be denoted by \(m\) and residents will be denoted by \(w\). We detail the generalization of this hospital-proposal algorithm below, where we also allow ties on the residents lists. This also may have several applications (for example, when residents have no preferences, only do have a list of acceptable hospitals). At the beginning all hospitals have the sorted list of its applicants. A hospital \(m\) prefers resident \(w\) to resident \(w^{\prime}\), if \(w\) has strictly higher priority, or they have the same priority (\(\mathrm{pri}(m,w)=\mathrm{pri}(m,w^{\prime})\)) and \(w^{\prime}\) has got some offer, but \(w\) has not. A hospital \(m\) is **active**, if it is under-subscribed and its list is non-empty.