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.
239
questions
-1
votes
0
answers
34
views
Champions League 36 team algorithm
Does anybody know exactly how the algorithm works that made the new draw for Champions League?
Wikipedia says:
The 36 teams were manually drawn and then automated software digitally drew their eight ...
- 257
0
votes
0
answers
33
views
Stable roommate problem (Stability in Seating Arrangements)
The Seating Arrangement Problem (SOP) is a specific variant of the Stable Roommates Problem (SRP) that I have defined. In the SRP, pairs of individuals are seated at two-person tables, whereas in the ...
0
votes
0
answers
13
views
What properties of a relation are necessary in a ranking system?
This question is partially about the methodology / process of formulating a question, prior to seeking an answer.
Let’s say the minimum we know at the outset is that a group of people can rank each ...
- 140
0
votes
1
answer
50
views
Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm
Consider a graph $ G = (V, E) $ where a vertex $ v \in V $ is designated as the center if it is connected to every other vertex $ u \in V $, such that both $ uv $ and $ vu $ are present in $ E $. A ...
1
vote
1
answer
37
views
Finding a matching with a specific weight
Polynomial-time algorithms for finding a maximum-weight matching in a weighted graph are well-known. Suppose I want not the maximum-weight matching, but a matching with a specific weight given as an ...
- 6,152
0
votes
0
answers
18
views
What algorithm should be used to find the closest set of dates?
I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
- 101
0
votes
1
answer
33
views
Optimizing Pairings Between Integers and Intervals for Maximal Matching
Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers ...
1
vote
0
answers
24
views
Algorithm to find most likely continuation of image over border from set of possible next images
Is there an algorithm that would fit in the following situation:
I have a sub image A of a larger image, and a set of sub images B that could (but not necessarily) share border with A. Now the ...
- 111
1
vote
1
answer
87
views
A problem maybe related to pattern-matching
Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$.
Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
- 11
2
votes
1
answer
33
views
How does additional assumptions increase approximation factor?
I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$.
Assume now that the weights in the graph ...
- 123
2
votes
1
answer
63
views
Weighted bipartite maximum cost with a fixed number of vertices
Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and:
Only a constant number $n$ of vertices ...
- 21
1
vote
0
answers
24
views
Stable Flow Problem with one sided preferences
I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
- 11
4
votes
1
answer
60
views
Max-min one-to-two matching
There are some $n$ people and $2 n$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person ...
- 6,152
1
vote
1
answer
495
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 ...
- 11
0
votes
0
answers
17
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 ...
- 11
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
71
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
125
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 ...
- 6,152
2
votes
0
answers
79
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 ...
5
votes
1
answer
381
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 ...
- 81
1
vote
1
answer
79
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 ...
- 443
1
vote
0
answers
125
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
145
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
38
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
159
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
83
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,892
2
votes
1
answer
57
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 ...
- 365
1
vote
1
answer
42
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
1
vote
1
answer
76
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 ...
- 160
0
votes
0
answers
26
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
40
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
252
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
77
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 ...
- 23
0
votes
1
answer
49
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
164
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 37
2
votes
1
answer
119
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 ...
- 443
1
vote
1
answer
222
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
89
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
69
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
44
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 ...
- 6,152
2
votes
0
answers
51
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
108
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
225
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
401
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
279
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
84
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
63
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
1k
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
2k
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