most recent 30 from http://mathoverflow.net 2013-05-22T19:13:07Z http://mathoverflow.net/feeds/question/64977 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem Glenn Habibi 2011-05-14T11:46:28Z 2011-05-14T14:56:57Z

<p>Suppose I had a complete bipartite graph with edges each given some numerical "cost" value. Is there a way to select a subset of those edges such that each vertex on each side of the graph is mapped to each vertex on the other (one to one) and the total "costs" is maximized (or minimized)?</p> <p>Has anyone ever formulated something equivalent to this?</p>

http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem/64987#64987 Max Alekseyev 2011-05-14T14:27:26Z 2011-05-14T14:27:26Z

<p>Looks like you are looking for maximum weighted bipartite matching - if so, see <a href="http://en.wikipedia.org/wiki/Maximal_matching#Maximum_matchings_in_bipartite_graphs" rel="nofollow">Wikipedia</a> for initial pointers.</p>

http://mathoverflow.net/questions/64977/bipartite-travelling-salesman-problem/64990#64990 Per Alexandersson 2011-05-14T14:56:57Z 2011-05-14T14:56:57Z

<p>You are looking for the max-flow-min-cut theorem: <a href="http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem</a></p>