Questions tagged [matching]

A matching (aka **Independent Edge Set**) in a simple graph is the set of pairwise non-adjacent edges i.e. no two edges have common vertex.

Filter by
Sorted by
Tagged with
4 votes
1 answer
429 views

state of the art of subset, set containment and partial match queries

The subset query problem is defined as: Given a list D of size N where the entries are subsets of a universe with ...
user avatar
5 votes
2 answers
8k views

The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
user avatar
  • 163
15 votes
2 answers
2k views

Sampling perfect matching uniformly at random

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am ...
user avatar
3 votes
1 answer
1k views

one-to-many matching in bipartite graphs?

Consider having two sets $L$ (left) and $R$ (right). $R$ nodes have a capacity limit. Each edge $e$ has a cost $w(e)$. I want to map each of the $L$ vertices to one node from $R$ (one-to-many ...
user avatar
4 votes
1 answer
4k views

Stable marriage problem with only one side having preferences [duplicate]

I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
user avatar
1 vote
1 answer
451 views

Weighted Matching with multiple assignments and min assignments

I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, ...
user avatar
  • 131
9 votes
1 answer
6k views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
user avatar
5 votes
2 answers
360 views

How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The ...
user avatar
  • 155
5 votes
3 answers
2k views

What is a fractional matching?

For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation ...
user avatar
  • 245
4 votes
1 answer
426 views

Assignment problem with no cost

I have a problem that I was able to conceptualize as following: Problem We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of ...
user avatar
3 votes
1 answer
6k views

Correctness proof: 2-approximation of greedy matching-algorithm

Input: number of edges and vertices, and array of all edges in graph. Output: array of edges that construct a matching, so that: $$\frac{\text{the number of edges in this matching}}{\text{the number ...
user avatar
  • 33
2 votes
1 answer
4k views

Assignment based on ranked preference

Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the <...
user avatar
3 votes
2 answers
2k views

Find a maximum matching in linear time

I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of ...
user avatar
6 votes
1 answer
2k views

Which algorithm can calculate an optimal allocation of students to projects?

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
user avatar
  • 63
4 votes
1 answer
1k views

Changing preference in Gale-Shapley algorithm?

Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm. If a man were to switch the order of a pair of women, ...
user avatar
4 votes
0 answers
158 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
user avatar
  • 141
2 votes
1 answer
313 views

Find a minimum-weight perfect b-matching, where b is even

How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b? A minimum-weight perfect b-...
user avatar
2 votes
1 answer
615 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
user avatar
0 votes
1 answer
106 views

Is the maximum matching problem trivial when the graph is complete?

I have a quick question. The maximum matching problem is an easy problem but not a trivial one. I was wondering that if the bipartite graph was complete, is it a trivial problem? I think we can just ...
user avatar
  • 91
0 votes
0 answers
174 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
user avatar