The "auction" algorithm

Note that the GIF animation presented on subsequent pages was not optimized for size: it comes in four bulky GIF files of nearly 10MB total. Hope to get it right in the future...

This is a sketch of the analogue computer suggested by M. Hénon for solving the assignment problem in optimization theory (see explanation in Section 4.2 of astro-ph/0304214). Clicking the NEXT link below will start an animation showing how the "auction" algorithm of D. Bertsekas works to compute the optimal assignment for the instance of the assignment problem represented by this machine.

Specifically, we let now the upper rods descend while keeping the lower rods fixed. Let us first drop the most distant upper rod...

[PREVIOUS] [NEXT]