The matching tag has no wiki summary.
7
votes
1answer
59 views
Sampling perfect matching uniformly at random
Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am ...
3
votes
1answer
71 views
Assignment problem with no cost
I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination ...
7
votes
2answers
137 views
An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore?
This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm ...
3
votes
1answer
36 views
Is matching with mismatches a special(parametrized) case of Closest String problem?
I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the ...
3
votes
2answers
65 views
Proof of the Stable Matching Problem
Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.
Theorem 1.2.3 - page 12:
In a man-optimal version of stable matching, each woman has worst
partner that ...
2
votes
2answers
113 views
Maximum weight matching
There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted ...
1
vote
1answer
224 views
3-dimensional matching approximation algorithm (implementation details)
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?
$X, ...
