Questions tagged [matching]
For questions on matchings, i.e. sets of disjoint edges of an undirected graph.
3
questions
2
votes
0answers
53 views
Problem classification: optimal weights for Weighted Arithmetic Mean
I want to write an optimisation problem then solve it, to get optimised weights to compute a final score using a weighted arithmetic mean.
The problem is as follows. I have an entity (an input vector ...
21
votes
1answer
283 views
Polynomially solvable problems with exponential extension complexity
The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
10
votes
1answer
102 views
Relationship between the Assignment Problem and the Stable Marriage Problem
Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the ...
