## 4 Implementation and Running Time
An active hospital makes an offer to the favorite resident on its list. A hospital \(m\) is **uncertain about the offer for**\(w\), if it is full, it is not an advantaged hospital, and moreover there is a resident \(w^{\prime}\) still on its list, whom it prefers to \(w\). When the list of a hospital is empty the first time, it becomes to an **advantaged hospital**, and starts proposing from its recovered list. When its list gets empty the second time, it remains inactive. A resident \(w\) is either **unoffered** or **offered**, if offered, he/she is called **precarious**, if his/her current offer is uncertain. A resident \(w\) prefers hospital \(m\) to \(m^{\prime}\) if either \(\mathrm{pri}(w,m)>\mathrm{pri}(w,m^{\prime})\), or \(\mathrm{pri}(w,m)=\mathrm{pri}(w,m^{\prime})\) and \(m\) is an advantaged hospital, while \(m^{\prime}\) is not. A resident always accepts a new offer, if either he/she is unoffered, or he/she is precarious. Otherwise he/she accepts, if the new offer is better for him/her than the previous one. _Hospital-proposing Algorithm_  
While there exists an active hospital \(m\), it offers to its favorite resident \(w\). If \(w\) immediately rejects this offer, \(m\) deletes \(w\) from its list. When a resident \(w\) gets a new offer from hospital \(m\), he/she always accepts this offer, if he/she is unoffered or precarious. He/she also accepts this offer, if he/she prefers \(m\) to the hospital he/she is actually assigned. Otherwise he/she rejects \(m\). If resident \(w\) accepted \(m\), then he/she rejects his/her previous offer, if there was one. If hospital \(m\) had offered to resident \(w\) and later \(w\) rejects it, then \(m\) deletes \(w\) from its list, except if \(w\) was precarious, in this case \(m\) keeps \(w\) on the list. If the list of hospital \(m\) becomes empty the first time, it becomes to an advantaged hospital, and starts proposing from its recovered list (keeping its actually assigned residents). However, it reactivates itself only if it is under-subscribed. When its list gets empty the second time then it remains inactive forever. After the algorithm finishes, the assignment is made along the non-rejected offers. Similarly to Section 4, this algorithm can also be implemented as a linear time local or global algorithm. First observe that our assumption is practically satisfied in this model, as hospitals usually get the extra information for each of theirs applicant about their place in his/her list. Residents may use the data structures of women without any modification, and hospital \(m\) will use data structures of men, with some additional values. It also stores \(p_{m}\), the priority of the last assigned resident, and value \(\phi_{m}\) of free places (capacity minus actually assigned residents, this quantity determines whether it is active or not) is also stored. This value \(\phi_{m}\) is easy to maintain: originally it is \(m\)'s capacity; if \(m\) makes a new offer, which is accepted, then it decreases \(\phi_{m}\), and if it gets a rejection from previously offered resident then it increases \(\phi_{m}\). An active hospital makes an offer as men do (for the first element of its dequeue). The main point is to be able to answer queries from a resident \(w\) about uncertainty of an offer made to him/her. Hospital \(m\) should answer yes, if the following three conditions hold: \(\phi_{m}=0\) and \(P_{m}>0\) and \(\mathrm{pri}(m,w)=p_{m}\). A strange situation can happen, if hospital \(m\) gets advantaged while resident \(w\) is assigned to it. After recovering its list, it can make a new proposal to the same resident \(w\) as an advantaged hospital. Remember that residents store the status of the hospital which made the current offer. In the situation described above he/she formally accept first the new offer (as it comes from a hospital with the same priority, but which is advantaged), and then \(w\) should reject the first offer. This needs only one extra bit of communication. Unfortunately these algorithms do not give better approximation ratio than HRGSA1.