All Questions
Tagged with matching-theory algorithms
57
questions
0
votes
0
answers
34
views
How DTW decides which element to take next?
I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one.
I do ...
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541
1
vote
0
answers
76
views
Polynomial Kernel For Minimum Maximal Matching Problem
Let $G$ be a graph, and $k$ be some non-negative integer. The goal is to decide whether there exists a maximal matching in $G$ on at most $k$ edges. This problem is also asked in https://www.mimuw.edu....
- 307
0
votes
0
answers
21
views
One to one mapping that maximize the minimum absolute difference
Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that
$$
\max \min_{i} |...
3
votes
1
answer
62
views
Greedy lemma Problem for matching spears to soldiers
The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is ...
- 307
2
votes
1
answer
102
views
Multiset Matching
Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
0
votes
0
answers
20
views
Algorithm for k sized matching in a complet weighted graph
as the Title suggest im looking for an algorithm for k sized matching in a weighted complet graph.
Any further literature is welcome.
- 1
3
votes
0
answers
122
views
Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched
Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the ...
- 73
0
votes
1
answer
102
views
Variant of minimum weight perfect matching problem with Hungarian algorithm
Given a complete bipartite graph $G=\{A+B,W\}$ with the number of vertices $|A|<|B|$, suppose I am looking for a subset $B'\subset B$ with $|B'|=|A|$ such that the minimum weight perfect matching ...
0
votes
0
answers
45
views
What is the order of a sum of arbitrary positive integers?
I am preparing a presentation about a version of Edmond's Blossom Algorithm as it has been
described by William Pulleyblank. The algorithm finds a maximum weight
b-matching for a graph $G = (V, E)$ ...
- 1
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,019
0
votes
0
answers
151
views
Maximum matching = Minimum odd vertex cover
Definition:
A set $CβV$ and a collection of subsets $π΅_1,β¦,π΅_πβV$ is an odd vertex cover if for every edge π either $πβ©πΆβ β
$ or $π β B_i$ for some π.
The cost of the odd vertex cover is ...
- 1
1
vote
1
answer
218
views
How to modify the hungarian algorithm for bipartite graphs with multiple edges with some already imposed connections
The Hungarian algorithm can be seen to take as input a complete weighted bipartite graph and outputs an optimal matching, maximising or minimising the sum of all the edges. Crucially, this algorithm ...
- 833
3
votes
1
answer
296
views
Are the results of the medical residency match algorithm unique? Variant of the stable marriage problem
Every year, applicants to medical residency programs each submit a strict ordering of a subset of available programs called a "rank order list" or "rank list" to the National ...
- 1,201
3
votes
1
answer
218
views
Algorithms for finding a Tutte-Berge maximizer
Let $G=(V,E)$ be a graph. The Tutte-Berge formula states that a maximum matching on $G$ has size $$\nu(G)=\frac12\left(|V|-\max_{U\subset V}(o(V-U)-|U|)\right)$$ with $o(V-U)$ the number of connected ...
- 6,842