Stable Marriage Problem and Its Complexity
Stable marriage problem is a matching problem that is usually found in mathematics or computer science. Meaning, alongside with the mathematics, this matching problem is used in the system of computer as well. This problem, which was first introduced by Gale and Shapely, is very classic. The core of this problem of stable matching is a mapping one set of elements with another set of elements. The problem of stable matching has this instance of men and women, which are considered as unstable if the preference of both a man and a woman are chooses of their own, and are considered stable if they are matched. From this, one can learn about the complexity of this problem.
Stable marriage problem is a matching problem that is usually found in mathematics or computer science. Meaning, alongside with the mathematics, this matching problem is used in the system of computer as well. This problem, which was first introduced by Gale and Shapely, is very classic. The core of this problem of stable matching is a mapping one set of elements with another set of elements. The problem of stable matching has this instance of men and women, which are considered as unstable if the preference of both a man and a woman are chooses of their own, and are considered stable if they are matched. From this, one can learn about the complexity of this problem.
Here is one example of stable marriage problem complexity. Given you have this n females and n males. Every person has m attributes. Not only that, every person is also indicating an accumulation that a possible candidate—from the given both males and females—should have. Because this problem is a problem of matchmaking, then a matching is considered to have a set of pairs. Every pair has to consist and hold fast a male to a female. The number of attributes that make at least one lucky person satisfied is considered as the satisfaction of a matchmaking. Then, there will occur a question like: is finding a matching with a maximum of satisfactory efficiently solvable? If it was not, then would it be NP-hard?
To solve this problem of complexity, the first step needed is to give a “Satisfaction level” letter k, and question whether there exists a matching in which everyone is matched with the one they have the least k desired attributes with. However, this accomplishment is only about the bipartite matching on a graph in which one can link a male and a female only if they get the satisfaction k from each others. The formula could be written like this; O(MN^2). If you want to return to the avast grade problem, you might do a binary search over k for extra log(m) factor at the moment.
No comments:
Post a Comment