Every matching can be associated with a cost - the sum of how every agent ranks their partner. In the egalitarian SRI problem we want to find a stable matching that minimises this cost. This optimality-criteria was proven to be NP-hard for an instance of SRI by Feder [1]}. More recently, rank-maximal and generous SRI and FC-SRI were shown to be NP-hard by Cooper [2]}. The minimum-regret SRI is an exception: Gusfield and Irving [3]} described an \(O(n^2)\)  algorithm, where \(n\)  is the number of agents.
