Assignment Problem (Weighted Bipartite Matching)

<span></span><p dir="ltr"><span><b>The Problem</b></span></p><p dir="ltr"><span>The assignment problem ( is important in market design. Think of it as minimizing the weight of a matching in complete bipartite graph on n and n.</span></p><p dir="ltr"><span><b>The Interface</b></span></p><p dir="ltr"><span>Input should be a weighted graph in the form Map&lt;String,Map&lt;String,double&gt;&gt;, in which each key is a node name, and its value is a map that links each neighbor to the weight (which may be positive, negative, or zero) of the edge connecting the two. If node B does not appear in the map corresponding to node A, the weight of the edge connecting them is assumed to be zero. Output a &#160;Map&lt;String,Object&gt; with two keys. One key is &#8220;assigment&#8221;, with corresponding value that is of class Map&lt;String,String&gt; (each key is a node, its value is the name of the node it was assigned to). The other key is the string &#8220;weight&#8221;, whose value is the weight of the matching (a double).</span></p><p dir="ltr"><span><b>The Algorithm</b></span></p><span>The wikipedia page describes a number of possibilities. It is probably easiest to formulate as a linear program and solve with binary Integer programming (</span>
  • {{comment.username}}
Bounty expires in
Bounty expired
(no tags)