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
1answer
7 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 ...
1
vote
0answers
34 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 ...
5
votes
1answer
59 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 \...
2
votes
0answers
26 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 ...
0
votes
1answer
97 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 ...
1
vote
1answer
59 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 ...
10
votes
0answers
61 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 ...
4
votes
1answer
116 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-...
0
votes
1answer
21 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 -...
1
vote
0answers
66 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 (...
4
votes
2answers
63 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(...
1
vote
1answer
25 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 ...
0
votes
0answers
7 views

Algorithm to pair respondents based on differences in answers to survey

I am having the following problem: I have asked a number of people 7 different binary questions. I now want to pair my respondents based on how different their answers to the questions were. The goal ...
0
votes
0answers
15 views

Generic real-time message/event matching engine

I'm looking for methods (any kind of combinations of algorithms & corresponding data structures) that can be used as a generic matching engine in case of arbitrary message/event types. Let me ...
1
vote
1answer
42 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 ...
1
vote
1answer
52 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 $...
0
votes
0answers
21 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
votes
0answers
23 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 ...
1
vote
0answers
38 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 ...
1
vote
1answer
50 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 ...
0
votes
1answer
27 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 ...
1
vote
1answer
96 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 ...
0
votes
1answer
48 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 ...
0
votes
0answers
15 views

Using bloom filters for high speed pattern matching in combination with Aho Corasick

I am implementing a new system for pattern matching in Intrusion Detection Systems for streaming data (network packets). I understand that bloom filters also produce false positives. Is there anyway ...
1
vote
0answers
64 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 ...
4
votes
0answers
55 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, ...
0
votes
0answers
29 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 \...
2
votes
2answers
160 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 $$ \...
1
vote
0answers
74 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 ...
1
vote
1answer
215 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 ...
0
votes
0answers
37 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", ...
0
votes
1answer
27 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 ...
0
votes
0answers
81 views

Gale-Shapley Stable matching where one man's preference list changes

Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale-Shapley algorithm with men proposing. Is there a stable matching instance such that: changing one man's preference list ...
0
votes
0answers
50 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 ...
1
vote
2answers
76 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 ...
1
vote
1answer
106 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 ...
2
votes
1answer
106 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{...
2
votes
1answer
198 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 ...
1
vote
1answer
32 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 ...
1
vote
1answer
33 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 ...
4
votes
2answers
72 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 ...
3
votes
1answer
194 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 ...
-1
votes
1answer
51 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|$?
1
vote
1answer
46 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$?
1
vote
1answer
82 views

Maximum one-to-many matching

Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is ...
3
votes
1answer
59 views

Combinatorial Problem similar in nature to a special version of max weighted matching problem

I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem. I have a ...
3
votes
1answer
206 views

Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
2
votes
1answer
159 views

Is there such a problem as b-Matching with different b values?

Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a ...
3
votes
0answers
32 views

How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
1
vote
1answer
91 views

Are these problems NP-Complete?

I got 2 decision problem that I need to answer if they are in P or they are NP complete: 1.Just like subset sum: given the integers or natural numbers ${\displaystyle w_{1},\ldots ,w_{n}}$ does ...