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.
192
questions
1
vote
0answers
60 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 (...
3
votes
1answer
35 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
20 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
11 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
33 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
46 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
20 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
34 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
59 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
27 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
11 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
61 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
48 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
146 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
73 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
184 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
34 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
26 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
68 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
44 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
51 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
60 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
82 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
178 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 ...
0
votes
0answers
63 views
Maximum cardinality matching of maximum weight
Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an ...
1
vote
1answer
25 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
31 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
69 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
193 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
39 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
45 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
52 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
56 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
197 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
90 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
24 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
89 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 ...
0
votes
0answers
33 views
Stable matching with dynamic preference lists
I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
1
vote
0answers
26 views
Blossom Algorithm
I have noticed that in the blossom algorithm, we need to find the blossom while finding the augmenting path. What will happen if I just know there is a blossom in a graph and the contracted graph has ...
0
votes
0answers
69 views
Special case of stable marriage
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
0
votes
0answers
118 views
Options for approaching stable marriage problem with unequally sized sets of elements/preferences
I am looking for an algorithm/code that will provide stable matching for two unequally sized sets of elements (clubs and students) with an unequal set of preferences. There is a large pool of students ...
3
votes
1answer
87 views
Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements
Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer. We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that
$\sum_{p, q = 1}^k A_{...
0
votes
0answers
20 views
Algorithm for b-matching on bipartite graph [duplicate]
I have a bipartite graph, where I want to assign nodes in Left set to Right set of nodes. There is a "b" constraint, which limits the maximum possible node degrees on the Right set.
Since it is a ...
-1
votes
1answer
104 views
Best and Worst options in Gale Shapley algorithm for an agent
Please consider the figure below. I have to find the best and worst options for W. From the preference list of W, the best option for W is D but there is no matching of W with D in all the 6 options. ...
1
vote
2answers
183 views
An algorithm to find the closest match between 2 arrays of RGB pixel tuples
So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.
Suppose we have 2 arrays of ...
