There is a group of $n$ men and $m$ women, and there is a symmetric dating between them (between the men and the women).
How can we find a match between the men and the women (depending to the dating) that will be a maximum match (by the size), but the sum of the ages of the women is minimal!
If there such a way for this I'd like to get proof for it because I try to find one with a proof and I can't :-(
Hall's theorem helps here or not?
But it something close, right?
I think about a variant of Belman-Ford algorithem? (Maybe there in no perfect matching, but I'm wonder if B-F algorithm can find maximum matching).
Thank you so much!
P.S. I don't how to say at English, but when I'm write maximum match I mean for the match with the maximum SIZE (you cant add more..)... (hope this is the right term).
Let me sketch an approach to solving this problem which replaces the minimum weight requirement with a maximum weight objective.
It requires finding at least one maximum matching in the bipartite graph $G \subseteq \{m_1,\ldots,m_n\} \times \{w_1,\ldots,w_m\}$ of "men" and "women".
If $G$ were the complete bipartite graph $K_{n,m}$ this would be trivial, as the maximum size of a matching is the minimum of $n$ and $m$, and knowing the size allows any subset of the larger "part" to be used for a perfect matching on that subgraph.
Let $V=n+m$ be the number of vertices and $E$ the number of edges in $G$. A well-known approach such as Ford-Fulkerson (1956) can find a maximum matching in $G$ in polynomial time, $O(VE)$. According to Alom, Das, and Islam (2010), Finding the Maximum Matching in a Bipartite Graph, this can be improved to "almost $O(E)$" (see Sec. 5). If true, this would be a very interesting result. However the algorithm of Hopcroft and Karp only requires $O(V^{1/2} E)$ steps in any case.
However your problem goes beyond asking for a maximum matching to one of these that minimizes the total ages of women in the matching. For this we could enumerate all possible maximum matchings and pick the one with the least total ages. See the Section below on methods for doing this, but the number of possible maximum matchings can grow exponentially.
Fortunately we can transform our requirement of minimizing the edge weights in a maximum matching in this specific problem to a requirement of maximizing the sum of edge weights. Intuitively let $M$ be a very large number, and replace the weight of the edge from $m_i$ to $w_j$ by $M-a_j$, where $a_j$ is the age of the woman $w_j$, the original weight of that edge.
Now maximizing the sum of the new edge weights in a matching will tend to maximize the size of the matching, because $M$ is very large. At the same time, among matchings of that maximum size, clearly the one with the largest sum of edge weights is the one for which the sum of corresponding $a_j$ is least.
To be rigorous about this, let $M \gt \sum_{j=1}^m a_j$. Suppose $k$ is the size of a maximum matching on $G$. Then for any matching of size less than $k$, the sum of edge weights is at most $(k-1)M$. For any matching of size $k$, the sum of edge weights is at least $kM - \sum_{j=1}^m a_j$. By our choice of $M$:
$$ (k-1)M \lt kM - \sum_{j=1}^m a_j$$
Therefore the maximum weight matching on $G$ with transformed weights is a maximum bipartite matching which minimizes the sum of ages $a_j$ appearing in the match.
Now a maximum weight bipartite matching can be found by a "greedy algorithm" that exploits the matroid structure of these problems.
Notes on enumerating all maximum matchings
The literature on enumerating all maximum matchings is fairly mature. T. Uno (1997) proposed Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs that begin by finding one maximum matching in $O(V^{1/2} E)$ time, using the ideas that go back to Hopcroft and Karp (1973). After this "pre-processing" phase the algorithm finds additional maximum matchings at a cost of $O(V)$ per maximum matching.
The paper Finding All Allowed Edges in a Bipartite Graph by Tamir Tassa (2011) seems to give a good survey of the known literature on finding maximum matchings. The application there is to finding all the edges of a bipartite graph which belong to some maximum matching, once a single maximum matching is known, in $O(V+E)$ time. The Introduction of this paper describes a matchmaking agency with a setup very similar to what is described in this Question.