<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>
Assignment Problem (Weighted Bipartite Matching)
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics.