Improving man-optimal stable matchings by minimum change of preference lists (Q1736562)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Improving man-optimal stable matchings by minimum change of preference lists
scientific article

    Statements

    Improving man-optimal stable matchings by minimum change of preference lists (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    26 March 2019
    0 references
    Summary: In the stable marriage problem, any instance admits the so-called \textit{man-optimal stable matching}, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man's preference list. We show that the optimization variant and the decision variant of this problem can be solved in time \(O(n^3)\) and \(O(n^2)\), respectively, where \(n\) is the number of men (women) in an input. We further extend the problem so that we are allowed to change \(k\) men's preference lists. We show that the problem is W[1]-hard with respect to the parameter \(k\) and give \(O(n^{2k+1})\)-time and \(O(n^{k+1})\)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when \(k=n\); we give \(O(n^{2.5}\log n)\)-time and \(O(n^2)\)-time algorithms for the optimization and decision variants, respectively.
    0 references
    combinatorial optimization
    0 references
    polynomial-time algorithms
    0 references
    stable marriage problem
    0 references
    man-optimal stable matching
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references