# AssignmentSolver

#### class AssignmentSolver extends AnyRef

A solver for weighted bipartite matching, also known as the assignment problem.

This does not use the Hungarian algorithm; instead it uses the augmenting paths algorithm which works by finding in sequence a best matching with one edge, a best matching with two edges, etc, until it find a best matching with maximal size. Then it goes back and returns the best overall matching out of those.

Transforming the best matching with n nodes into the best matching with n+1 nodes is done by finding the best augmenting path: define a new graph with a source connected with zero weight edges to the unmatched nodes on the "left" side of the matching, and likewise a target connected to the unmatched nodes on the right side. For the bipartite graph, have the edges in the matching have positive weight equal to their cost and going from right to left, while edges not in the matching have negative weights equal to their costs and go from left to right.

Then a shortest path from the source to target will necessarily add one edge to the matching for each edge it removes, and add one more edge than that.

To see a proof of this algorithm see the lecture notes in http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/18-maxflowext.pdf

Note that we can't use Dijkstra for shortest-paths because of the negative-weighted edges. We can't have negatively weighted cycles because the existence of such a cycle would imply that the current state is not a maximal matching with its size.

This is useful for implementing the CEAF evaluation metrics in coreference resolution, which assign scores between pairs of truth and returned entities and define the precision and recall of a clustering as a function of the best possible matching between truth and returned clusters.

Linear Supertypes
AnyRef, Any
Ordering
1. Alphabetic
2. By inheritance
Inherited
1. AssignmentSolver
2. AnyRef
3. Any
1. Hide All
2. Show all
Visibility
1. Public
2. All

### Value Members

1. #### final def !=(arg0: AnyRef): Boolean

Definition Classes
AnyRef
2. #### final def !=(arg0: Any): Boolean

Definition Classes
Any
3. #### final def ##(): Int

Definition Classes
AnyRef → Any
4. #### final def ==(arg0: AnyRef): Boolean

Definition Classes
AnyRef
5. #### final def ==(arg0: Any): Boolean

Definition Classes
Any
6. #### final def asInstanceOf[T0]: T0

Definition Classes
Any
7. #### def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
8. #### final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
9. #### def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
10. #### def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
11. #### final def getClass(): Class[_]

Definition Classes
AnyRef → Any
12. #### def hashCode(): Int

Definition Classes
AnyRef → Any
13. #### final def isInstanceOf[T0]: Boolean

Definition Classes
Any
14. #### final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
15. #### final def notify(): Unit

Definition Classes
AnyRef
16. #### final def notifyAll(): Unit

Definition Classes
AnyRef

19. #### final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
20. #### def toString(): String

Definition Classes
AnyRef → Any
21. #### final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
22. #### final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
23. #### final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )