Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
1 vote
1 answer
29 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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
16 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 ...
Christian Webb's user avatar
0 votes
1 answer
29 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 ...
jack norton's user avatar
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 ...
Nyxeria's user avatar
  • 111
1 vote
1 answer
78 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 ...
Tigerion's user avatar
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 ...
mNugget's user avatar
  • 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 ...
Lozan's user avatar
  • 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 ...
Finn's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
382 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 ...
void's user avatar
  • 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 ...
void's user avatar
  • 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 ...
akhil's user avatar
  • 11
0 votes
1 answer
66 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 ...
akhil's user avatar
  • 11
1 vote
1 answer
121 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 ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
77 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 ...
Harry Vinall-Smeeth's user avatar
5 votes
1 answer
360 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 ...
Chaya's user avatar
  • 81
1 vote
1 answer
74 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 ...
SVMteamsTool's user avatar
1 vote
0 answers
117 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....
Reema's user avatar
  • 11
0 votes
0 answers
133 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 ...
scubadude22's user avatar
-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 ...
AndyBrondy7's user avatar
1 vote
1 answer
138 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. ...
JohnHernandez's user avatar
3 votes
0 answers
78 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 ...
Craig Gidney's user avatar
  • 5,862
2 votes
1 answer
56 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 ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
41 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 ...
mdatsev's user avatar
  • 111
1 vote
1 answer
68 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 ...
muser's user avatar
  • 150
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 +...
Reem Aljunaid's user avatar
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 ...
RJ94's user avatar
  • 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 \...
3nondatur's user avatar
  • 457
1 vote
2 answers
198 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 ...
Sam's user avatar
  • 11
1 vote
0 answers
72 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 ...
ZenPyro's user avatar
  • 23
0 votes
1 answer
45 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 ...
Keio203's user avatar
  • 257
1 vote
1 answer
152 views

Max matching algorithm lemma approximation algorithm

We have this algorithm which is supposed to find max matchings. ...
kostger's user avatar
  • 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 ...
SVMteamsTool's user avatar
1 vote
1 answer
206 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 ...
Chen Reddy Sundeep's user avatar
2 votes
2 answers
82 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 ...
JMenezes's user avatar
  • 135
1 vote
1 answer
66 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 ...
zdm's user avatar
  • 1,046
2 votes
1 answer
42 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 ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
46 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 ...
NiRvanA's user avatar
  • 159
0 votes
1 answer
107 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 ...
NiRvanA's user avatar
  • 159
0 votes
1 answer
219 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 ...
StudentOrint's user avatar
1 vote
1 answer
337 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 ...
Nick's user avatar
  • 25
1 vote
0 answers
269 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 ...
shima's user avatar
  • 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 \...
0410's user avatar
  • 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 ...
NiRvanA's user avatar
  • 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 ...
Fimpellizzeri's user avatar
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 ...
Tushar Saha's user avatar
10 votes
0 answers
99 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 ...
Erel Segal-Halevi's user avatar
4 votes
1 answer
159 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-...
Erel Segal-Halevi's user avatar
0 votes
1 answer
193 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 -...
syahiruddin's user avatar
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 (...
user143196's user avatar

1
2 3 4 5