Stack Overflow
Stack Overflow

Questions tagged [stable-marriage]

Use this tag for algorithms which solve the stable marriage problem from graph theory.

Use this tag for algorithms which solve the stable marriage problem from graph theory.

32 questions
5
votes
3 answers

Algorithm to verify stable matching?

I know using Gale-Shapley is guarantee to find a stable matching, but for a given matching, how do we verify that it is a stable matching? In other words, what conditions should I consider to validate that it is a stable matching?
soc yun
  • 57
  • 1
  • 2
5
votes
4 answers

Matching Algorithm (Java)

I am writing an algorithm to match students with different groups. Each group has a limited number of spots. Each student provides their top 5 choices of groups. The students are then placed into groups in a predetermined order (older students and…
Dylan Wheeler
  • 6,928
  • 14
  • 56
  • 80
4
votes
2 answers

Variation of stable marriage -- is there always a stable "solution"?

The following problem is from "Algorithm Design" by Jon Kleinberg and Éva Tardos, Chapter 1, Exercise 3. I shortened down the description as much as possible (my annotations in brackets or outside the quote block) Suppose we have two television…
John
  • 2,015
  • 5
  • 23
  • 37
2
votes
2 answers

Stable Marriage Problem - Empty preference lists

I've been trying to learn about the Stable Marriage Problem and was wondering what happens if someone doesn't fill in their preference list - at all. I've read up about the problem with regards to incomplete lists and ties etc. but can't seem to see…
Jamie
  • 25
  • 8
2
votes
1 answer

Is there any python code or a modification for the Gale Shapley algorithm so it can solve stable marriage problem with incomplete preference lists

I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed interest only in a subset of women and vice versa. I…
ESDAIRIM
  • 611
  • 4
  • 12
2
votes
3 answers

Brute force stable marriage, How to implements all possible pairs between 2 lists?

I'm trying to implement an algorithm to find all stable marriage solutions with a brute force approach without the Gale-Shapley algorithm (because it gives us only 2 of them). I'm using the checking mechanism found in rosettacoode but I'm having an…
nicanz
  • 347
  • 1
  • 2
  • 11
2
votes
1 answer

What is the largest number of solutions to an instance of Stable Marriage?

Every Stable Marriage problem has at least one solution. However, how to know the largest number of solutions to a stable marriage problem? The Gale-Shapley algorithm can only find one man-optimal solution. If we use woman-optimal method to run…
microbit
  • 319
  • 3
  • 10
1
vote
1 answer

Best matching algorithm for an economic simulation?

I want to find the best matching algorithm to recreate an economic simulation. I will create differents groups of customers. Each group will have particular parameters that will determine what the customers wants to buy. Example of those parameters…
NLemay
  • 2,331
  • 3
  • 29
  • 45
1
vote
1 answer

How to approach Stable Marriage Problem with restricted pairs

Let's say we have a version of the stable marriage problem with the addition that some pairs are restricted based on certain preferences, e.g. whether or not someone lives in a different city and whether or not that person is okay with long-distance…
Cole
  • 11
  • 3
1
vote
1 answer

Stable Marriage problem variant that only cares about the preference of one party

I am looking for a variant of the stable marriage problem. That is, only one party has a preference for the other party. The other party must have no preference for the first party. An example: a set of people have a preference list for a set of…
twit
  • 19
  • 4
1
vote
1 answer

stable marriage problem happiness coefficient

I am trying to solve this problem for an online judge: There are sets of n men and n women. Each man evaluates the women with numbers from 1 to n, giving them different grades, and each woman estimates similarly to the men from 1 to n. This all…
v_head
  • 759
  • 4
  • 13
1
vote
2 answers

Optimal grouping/clustering of items in groups with minimum size

I am looking for an algorithm that solves the following problem: Given: a set of items and their similarity matrix. Goal: group these items in "clusters" of minimum size m Conditions: There are no cluster-like structures in the dataset, as shown…
lkegel
  • 193
  • 9
1
vote
1 answer

Stable Marriage and its extension

I have two questions about stable marriage problem. Given n men and n women, where each person has ranked all members of the opposite sex with an unique number between 1 and n in order of preference, marry the men and women together such that…
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
1
vote
3 answers

counter example of a stable matching

I am currently reading an algorithm book and came across the Stable Matching Problem. And a question came to mind that I'm curious about, but the book doesn't answer. The question is: For any matching, if it is not stable, pick any blocking pair(w,…
ZHOU
  • 1,151
  • 2
  • 12
  • 27
0
votes
1 answer

Are the results of the medical residency match algorithm unique?

Every year, applicants to medical residency programs each submit a strict ordering of a subset of available programs called a "rank order list" or "rank list" to the National Resident Matching Program (NRMP) that reflects each of their preferences.…
rorty
  • 123
  • 3
1
2 3