Questions tagged [matching]

For questions on matchings, i.e. sets of disjoint edges of an undirected graph.

Filter by
Sorted by
Tagged with
3
votes
1answer
29 views

Finding an augmenting path or cycle in weighted graph

Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
5
votes
2answers
187 views

Counting the number of matchings in a complete bipartite graph

I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $n!$ perfect matchings in the ...
2
votes
0answers
63 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
289 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
112 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 ...