auction_match: Compute optimal (maximal) weighted assignment
% and the corresponding "lattice of dual prices" supporting the
% optimal assignment.
% auction_match(disMatrix) computes the optimal assignment for the
% given rectangular value matrix, for example the assignment
% of bidders (in rows) to objects (in columns) and vice versa.
% [assignment,r,p,u,v,value] = ASSIGNMENTOPTIMAL(DISTMATRIX) returns the assignment
% vector (in assignment) and the overall value (in value) and
% v: surplus of columns if columns were bidding for rows.
% u: the corresponding prices of rows.
% p: prices for columns if rows were bidding for columns
% r: the corresponding surplus of rows.
%
% Note that (p,-r) forms the lower corner and (v,-u) forms the
% upper corner in the lattice of optimal dual vector supporting
% the optimal assignment thus giving the complete lattice.
% Ref. the survey "From the Assignment Model to Combinatorial Auctions"
% by S. Bikhchandani and J. Ostroy
% This is update of the assignment code by Markus Buehren which used Munkres
% Algorithm for MINIMAL weighted matching. A description of Munkres algorithm
% (also called Hungarian algorithm) can easily be found on the web. |
