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.
206
questions
0
votes
0
answers
13
views
Comparing two poses of a point cloud
I have an unstructured point cloud for which I determine pose information described as a similarity transform (rotation matrix and translation vector). In my setting, several independent poses are ...
- 4,537
1
vote
1
answer
28
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 37
2
votes
1
answer
81
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 ...
- 379
1
vote
1
answer
59
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
34
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 ...
- 123
1
vote
1
answer
42
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,016
2
votes
1
answer
23
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,726
2
votes
0
answers
27
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 ...
- 149
0
votes
1
answer
41
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 ...
- 149
0
votes
1
answer
71
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
26
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
95
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
64
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
38
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 ...
- 149
1
vote
1
answer
341
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
1
answer
387
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
69
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,726
4
votes
1
answer
128
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,726
0
votes
1
answer
37
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
70
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
4
votes
2
answers
93
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(...
- 363
1
vote
1
answer
35
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,824
1
vote
1
answer
59
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
59
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,824
0
votes
0
answers
23
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,824
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
43
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,726
1
vote
1
answer
54
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,871
0
votes
1
answer
29
views
Match unpaired points between two sets
I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points ...
- 133
1
vote
1
answer
355
views
Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)
I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:
Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
...
- 157
0
votes
1
answer
53
views
How are matchings a lower bound for an approximate vertex cover?
I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching ...
- 659
1
vote
0
answers
65
views
Disjoint groups using maximum matching
In the 3-Path Packing problem, we are given an undirected graph $G$ and a parameter
$k \in \mathbb{N} \cup \{0\}$. We need to answer Yes/No if there exists a collection of $k$ vertex disjoint paths on ...
- 103
4
votes
0
answers
56
views
Find an optimal matching in a complete graph
I have a complete edge-weighted graph with $n$ vertices (and therefore $n\cdot(n-1)/2$ edges). I want to find a complete matching (i.e., perfect matching) in which the quotient $sum_G/A_G$ is maximal, ...
- 41
0
votes
0
answers
30
views
Stochastic matching with fewer queries
Given a graph $G = (V,E)$ and a probability $p \in [0,1]$ with which each edge is sampled from the graph $G$. The goal of the stochastic matching problem with fewer queries is to find a subgraph $H \...
- 1
2
votes
2
answers
203
views
Maximum weight perfect matching in general graphs
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\...
- 2,871
1
vote
0
answers
75
views
Can somebody please explain what are these variables doing here?
I have this algorithm:
I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
- 121
2
votes
1
answer
279
views
calculating the string similarity of an optimal alignment
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
- 71
0
votes
0
answers
44
views
Is there an approximation algorithm for the three-person stable roommates problem?
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
- 101
0
votes
1
answer
28
views
Matching with specific cardinality
In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
- 131
0
votes
0
answers
65
views
Computing a fractional matching of maximum product in a bipartite graph
Given a bipartite graph $(X\cup Y, E)$ with edge weights, it is easy to find a matching in which the product of weights is maximum: replace each edge weight with its logarithm, and find a matching in ...
- 5,726
1
vote
2
answers
105
views
Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
- 111
1
vote
1
answer
427
views
Can't wrap my head around on building a suffix table for Boyer Moore
My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:
k
suffix
d2
1
...
- 113
2
votes
1
answer
129
views
maximum cardinality weighted matching
I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.
Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{...
- 131
2
votes
1
answer
226
views
Find optimal local alignment of two strings with restrictions
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local ...
- 165
1
vote
1
answer
45
views
Concept of M-augmenting path to find a larger matching than $M$
I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if:
The ...
- 305
1
vote
1
answer
36
views
splitting of people betwen groups with group prioritiy list per person
Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most ...
- 11
4
votes
2
answers
73
views
How difficult is this matching-like problem?
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
- 43
3
votes
1
answer
195
views
Game on the graph with matchings
The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
- 137
-1
votes
1
answer
63
views
Maximal vs maximum matchings
Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
- 99
1
vote
1
answer
50
views
Independent sets into which all the vertices of the graph can be split
How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
- 137