org.apache.hadoop.hbase.util

Class MunkresAssignment

java.lang.Object

org.apache.hadoop.hbase.util.MunkresAssignment

@InterfaceAudience.Private
public class MunkresAssignment
extends Object

Computes the optimal (minimal cost) assignment of jobs to workers (or other analogous) concepts given a cost matrix of each pair of job and worker, using the algorithm by James Munkres in "Algorithms for the Assignment and Transportation Problems", with additional optimizations as described by Jin Kue Wong in "A New Implementation of an Algorithm for the Optimal Assignment Problem: An Improved Version of Munkres' Algorithm". The algorithm runs in O(n^3) time and need O(n^2) auxiliary space where n is the number of jobs or workers, whichever is greater.

Constructor Summary

Constructors

Constructor and Description
MunkresAssignment(float[][] costMatrix) Construct a new problem instance with the specified cost matrix.

Method Summary

Modifier and Type	Method and Description
int[]	solve() Get the optimal assignments.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MunkresAssignment

public MunkresAssignment(float[][] costMatrix)

Construct a new problem instance with the specified cost matrix. The cost matrix must be rectangular, though not necessarily square. If one dimension is greater than the other, some elements in the greater dimension will not be assigned. The input cost matrix will not be modified.

Parameters:

costMatrix -

Method Detail

solve

public int[] solve()

Get the optimal assignments. The returned array will have the same number of elements as the number of elements as the number of rows in the input cost matrix. Each element will indicate which column should be assigned to that row or -1 if no column should be assigned, i.e. if result[i] = j then row i should be assigned to column j. Subsequent invocations of this method will simply return the same object without additional computation.

Returns:

an array with the optimal assignments