Packages

class Hungarian extends AnyRef

The Hungarian is an O(n^3) implementation of the Hungarian algorithm (or Kuhn-Munkres algorithm). Find the maximum cost set of pairings between 'm' x-nodes (workers) and 'n' y-nodes (jobs) such that each worker is assigned to one job and each job has at most one worker assigned. It solves the maximum-weighted bipartite graph matching problem.

maximize sum i = 0 .. m-1 { cost(x_i, y_i) }

Caveat: only works if 'm <= n' (i.e., there is at least one job for every worker).

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. Hungarian
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Instance Constructors

  1. new Hungarian(cost: MatrixD)

    cost

    the cost matrix: cost(x, y) = cost of assigning worker to job

Value Members

  1. def solve(): Double

    The main procedure to solve an assignment problem by finding initial pairings and then finding augmenting paths to improve the pairings/assignments.