### Highlights from Rectangular maximal assignment with lattice of dual price

Be the first to rate this file! 13 Downloads (last 30 days) File Size: 9.41 KB File ID: #14251 Version: 1.0

# Rectangular maximal assignment with lattice of dual price

### Anuj Kumar (view profile)

13 Mar 2007 (Updated )

Computes the maximal ractangular matching as well as the prices and surplus in both cases 1) rows bi

File Information
Description

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.

Acknowledgements

Functions For The Rectangular Assignment Problem inspired this file.

MATLAB release MATLAB 7 (R14)