Description
<span></span><p dir="ltr"><span><b>The Problem</b></span></p><p dir="ltr"><span>The assignment problem (http://en.wikipedia.org/wiki/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<String,Map<String,double>>, 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  Map<String,Object> with two keys. One key is “assigment”, with corresponding value that is of class Map<String,String> (each key is a node, its value is the name of the node it was assigned to). The other key is the string “weight”, 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 (https://algorithmia.com/algorithms/JaCoP/BinaryIntegerProgramming).</span>


requests
Solve the weighted bipartite matching problem, aka the "assignment problem" 


requests
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. 