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.
228
questions
0
votes
0
answers
93
views
Finding all stable matchings in stable marriage problem
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
0
votes
0
answers
13
views
Finding all stable matchings in stable marriage problem [duplicate]
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
0
votes
1
answer
48
views
Reductions to perfect matching
Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
- 1
1
vote
0
answers
32
views
Find an assignment discarding a subset of possible assignments
We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task.
The number of possible assignments is $N!$. Let us call this set of all possible ...
- 11
0
votes
1
answer
56
views
Number of matchings in a bipartite graph having missing edges
Suppose we have a bipartite graph with $N$ vertices on either side.
In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$.
Now ...
- 11
1
vote
1
answer
100
views
High-multiplicity maximum-weight matching
There are $n$ people and $m$ jobs. We would like to assign at most one job to each person.
For each person,job pair, there is a positive value determining the fitness of this person to that job. The ...
- 5,730
2
votes
0
answers
75
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
4
votes
1
answer
326
views
Partitioning a graph into connected pairs and triplets
We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer.
When $k=2$, the problem is equivalent to the perfect matching problem which is ...
- 71
1
vote
1
answer
58
views
Reducing the min weight perfect matching problem to a T-join
My lecture notes for $T$-joins states:
If $T = V$ then $T$ -joins of cardinality $V/2$
are exactly the perfect matchings of $G$ = $(V ,E)$.
So, the minimum weight perfect matching problem can be ...
- 423
1
vote
0
answers
106
views
Preference based assignment problem to maximize utility
I am studying an optimization problem which can be recast as an LP I have described below. I wish to understand the structure of optimizers of the original problem by studying the optimizers of the LP....
- 11
0
votes
0
answers
98
views
Budgeted min cost max flow in bipartite where the flows must also be a matching set
I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
-1
votes
1
answer
33
views
Pattern Matching Variant Problem
Given string P with length n, and a function A on P [n] --> [n] that does the following:
For every 1 <= k <= n
A on P [k] = { the maximum index i such that P[1...i] = P[k...k+i-1]
Write an ...
1
vote
1
answer
96
views
pairing numbers and intervals
subject: pairing numbers and intervals
Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. ...
3
votes
0
answers
73
views
Lights-out! on a hex grid with buttons on nodes and lights on faces
Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below:
Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
- 5,802
2
votes
1
answer
51
views
For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$
As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$.
The general goal of the proof is to show that ...
- 315
1
vote
1
answer
36
views
Assign items from inventory to people maxmizing the number of satisfied people
We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We ...
- 111
0
votes
1
answer
48
views
Choosing root for maximum matching in tree
This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part.
Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
- 140
0
votes
0
answers
24
views
Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?
Using the algorithm provided by this paper, they said that:
The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
0
votes
1
answer
21
views
What is the associative operator ⊕ in graph matching? and How does it works?
I read a paper about Parallel Matching, and I didn't understand what the associative operator ⊕ in the following lemma/proof and how does it works in vertices and edges in the graph?
Lemma 3. Using ...
- 1
1
vote
1
answer
37
views
How to argue that an $A$-covering matching exists in this bipartite graph?
In lecture the following was mentioned in the context of matchings in bipartite graphs:
Let $U$ be a finite set and let $\mathcal{S}$ be a family of subsets of $U$.
For $u \in U$ let $r(u) := \lvert \...
- 457
1
vote
2
answers
142
views
Matching students with companies based on their preference
I have a list of companies with n timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to.
Is ...
- 11
1
vote
0
answers
54
views
Understanding how the total # of comparisons is derived for the worst case in the "Brute-Force String Matching" algorithm
The Total number of comparisons for the worst case in the "Brute-Force String Matching" algorithm is: (n-m+1) where ...
- 13
0
votes
1
answer
34
views
Proving that this matching is stable
Consider the stable marriage problem with $n$ men and $n$ women. Let $A$ and $B$ be two stable matchings, and suppose that we form a new matching $C$ by assigning to each men his favorite partner ...
- 257
1
vote
1
answer
117
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 37
2
votes
1
answer
109
views
Proving that the number of leaves in a tree >= number of unmatched vertices
Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every ...
- 423
1
vote
1
answer
168
views
Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?
I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2.
Set cover problem with sets of size 2
The ...
2
votes
2
answers
74
views
Matching problem in bipartite network with more than one edge per vertex
I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For ...
- 135
1
vote
1
answer
60
views
Find a perfect matching with weights as close as possible to each other
Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
- 1,046
2
votes
1
answer
40
views
Using algorithm for weighted graphs when the weights are vectors
Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem ...
- 5,730
2
votes
0
answers
41
views
Proving existence of sinkless orientation on graph with minimum degree 2
I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge.
As a ...
- 159
0
votes
1
answer
62
views
Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n
Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$.
My attempt:
At each step I will also remove the edge from the graph that I am adding to the ...
- 159
0
votes
1
answer
200
views
Find a maximum matching in linear time - How to prove it?
Let B be an undirected tree with |V| nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime O(|V|).
I understand that the solution ...
1
vote
1
answer
174
views
Max-Min Weighted Matching
The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
- 25
1
vote
0
answers
236
views
Graph in which greedy algorithm for maximum matching is a 2-approximation
Here is a greedy algorithm for maximum bipartite matching:
Iteratively select an edge that is not incident to previously selected edges.
This algorithm returns a 2-approximation, and runs in linear ...
- 111
5
votes
1
answer
82
views
The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?
Here is the full version of the problem I'm dealing with.
Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \{S,T\}$). For a subset $C \...
- 75
2
votes
0
answers
57
views
Size of the maximum matching in arbitrary graph
I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $ G $.
My claim is that, it is equivalent to find a global min cut on ...
- 159
1
vote
1
answer
910
views
How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time
This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani.
Specifically, the problem statement is:
Give a linear-time algorithm that ...
- 235
1
vote
3
answers
1k
views
How can we express value of cosine similarity of two documents into percentage?
We were doing project work for plagiarism checking. For this purpose, we have taken a term frequency vector of two documents and measured the similarity using a cosine similarity measure. The value of ...
- 27
10
votes
0
answers
92
views
Maximum matching with social distancing
Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
- 5,730
4
votes
1
answer
154
views
Maximum-weight matching with a bounded number of fractional edges
In graphs with odd cycles, the maximum weight of a fractional matching may be higher than that of a standard matching. For example, in a cycle of length 3, where all edges have weight 1, the maximum-...
- 5,730
0
votes
1
answer
139
views
Algorithm best compare similarities between two data sets in percentage
I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions.
Example:
Q1: Do you prefer physically demanding tasks?
A1: Nope Maybe Yes -...
- 101
1
vote
0
answers
72
views
Hardness result for online matching
Currently studying the following paper:
"Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014
In which they present Theorem 2 as a hardness result for online maxmin matchings (...
- 11
5
votes
2
answers
266
views
How to match two point sets to minimize total distance?
Let's say we have two sets $X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$, $Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that
$$D = \sum_{i=1}^n d(x_i, y_{\pi(...
- 373
1
vote
1
answer
96
views
Three dimensional matching expressed as SAT
The posting in the website Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING seeks $3SAT$ as a $3$ dimensional matching instance.
I am looking to solve the converse problem. How to solve three ...
- 2,881
1
vote
1
answer
133
views
Algo to match students to universities (only students choose & rank)
I'm trying to develop an algorithm in Ruby to allocate one university to each student of a list. As opposed to Gale-Shapley algorithm, universities do no choose nor rank students; only students make a ...
- 11
1
vote
1
answer
69
views
What is the comparator circuit?
The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths.
What is the comparator gate constituted from?
Structurally why is it believed $...
- 2,881
0
votes
0
answers
26
views
What is the depth of comparator circuit required in Gale Shapely and STCONN?
Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).
What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
- 2,881
2
votes
0
answers
25
views
Subgraph isomorphism index/precomputation
I'm currently working on problem in which a set of graphs $T=\{t_1,\dots,t_n\}$ is given and fixed.
Given a graph $m$ I want to check which of the $t_i$ are subgraphs of it, as quick as possible.
Is ...
- 121
1
vote
0
answers
64
views
Hardness of multiplicative vs. additive approximation
Chlebik and Chlebikova prove that the problem "maximum 3-dimensional matching" is NP-hard to approximate within a multiplicative factor of $95/94$.
This means that, unless $P=NP$, there is ...
- 5,730
1
vote
1
answer
64
views
a lower bound for the maximum fraction of matchings not containing an edge
I am trying to prove the following statement (from book, page 317):
Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of ...
- 2,932