Code or psuedo-code for linear bottleneck assignment (LBAP)? [closed]

Question

I'm building a robot simulator where I have n robots that need to go to n separate locations. All the robots start moving concurrently. When a robot gets to its assigned location it stops moving. The total amount of time needed for all robots to reach their locations is determined by the longest length that a given robot needs to reach its assigned location. I'd like to minimize this longest length by clever assignment of destinations to robots.

Apparently this problem is the "Linear bottleneck assignment problem".

I couldn't find any code to solve this problem. Anyone have any pseudo-code, or actual code (any language fine, Ruby/Java preferred) to solve this efficiently?

Answer 1

The threshold algorithm is one of the standard algorithms for solving the linear bottleneck assignment problem. A quick search didn't turn up pseudocode that I could easily copy and paste here, but pseudocode is given on page 175 of Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, and Silvano Martello. Here's the Google books link to the relevant page. A few pages later they give another algorithm that exploits duality, but I'm not as familiar with that one.