A primal based task allocation method

Download code
  • This optimal assignment algorithm is a primal method, which differs from most of current popular assignment algorithms. The algorithm is improved over Balinski-Gomory's method (1964), and we have redesigned the algorithmic procedures such that it can be well applied to the distributed systems.
    The theoretical running time is O(n^3 lg n), and this algorithm is easy to implement and easy to achieve the theoretical time complexity (the above code has reached this time complexity).


  • For more details, please refer to paper:
    Lantao Liu, Dylan Shell. "A Distributable and Computation-flexible Assignment Algorithm: From Local Task Swapping to Global Optimality". Proceedings of Robotics: Science and Systems. Jul 2012.