Interval Hungarian Method

Download code
  • Interval Hungarian algorithm is a sensitivity analysis method but runs very fast. For each matrix entry, it computes the allowable interval that does not violate current optimal solution.
    The theoretical time complexity for each interval computation is O(n^4). Parallel computation of intervals can also be easily implemented.

  • For more details, please refer to paper:
    Lantao Liu, Dylan Shell. "Assessing Optimal Assignment under Uncertainty: An Interval-based Algorithm". International Journal of Robotics Research (IJRR). vol. 30, no. 7, pp 936-953. Jun 2011.