## Class KuhnMunkresStern

• @Reference(authors="K. L. Stern",
title="The Hungarian Algorithm for the Assignment Problem",
booktitle="Online",
url="http://software-and-algorithms.blogspot.com/2012/09/the-hungarian-algorithm-for-assignment.html",
bibkey="web/Stern12")
public class KuhnMunkresStern
extends KuhnMunkresWong
A version of Kuhn-Munkres inspired by the implementation of Kevin L. Stern. This approach shares some ideas of KuhnMunkresWong, but works on columns instead of rows first. So far, we have not found a good reference why this works much faster is practice; but it does.

References:

K. L. Stern
The Hungarian Algorithm for the Assignment Problem
http://software-and-algorithms.blogspot.com/2012/09/the-hungarian-algorithm-for-assignment.html

Since:
0.8.0
Author:
Erich Schubert
• ### Field Summary

Fields
Modifier and Type Field Description
private double[] cmin
Minimum value of non-marked row, for each column.
private int[] cptr
Pointer to the minimum non-marked value, for each column; but initially to the starting row.
• ### Fields inherited from class elki.utilities.datastructures.KuhnMunkresWong

cadj, radj, rmin, rptr
• ### Fields inherited from class elki.utilities.datastructures.KuhnMunkres

cmark, cost, csel, minc, minr, rmark, rsel, selected
• ### Constructor Summary

Constructors
Constructor Description
KuhnMunkresStern()
• ### Method Summary

All Methods
Modifier and Type Method Description
protected double findUncoveredMinimum()
Find the minimum in the uncovered rows.
protected void initUncoveredMinimum()
Initialize values for finding the minima efficiently.
protected void removeCost​(double h)
Remove cost h (if > 0) found to be unavoidable.
int[] run​(double[][] cost)
Perform the Kuhn-Munkres algorithm.
• ### Methods inherited from class elki.utilities.datastructures.KuhnMunkresWong

costOf, initialCover, initialize
• ### Methods inherited from class elki.utilities.datastructures.KuhnMunkres

debugLogMatrix
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### cptr

private int[] cptr
Pointer to the minimum non-marked value, for each column; but initially to the starting row.
• #### cmin

private double[] cmin
Minimum value of non-marked row, for each column.
• ### Constructor Detail

• #### KuhnMunkresStern

public KuhnMunkresStern()
• ### Method Detail

• #### run

public int[] run​(double[][] cost)
Description copied from class: KuhnMunkresWong
Perform the Kuhn-Munkres algorithm.
Overrides:
run in class KuhnMunkresWong
Parameters:
cost - Cost matrix
Returns:
Selected columns, per row
• #### initUncoveredMinimum

protected void initUncoveredMinimum()
Description copied from class: KuhnMunkresWong
Initialize values for finding the minima efficiently.
Overrides:
initUncoveredMinimum in class KuhnMunkresWong
• #### findUncoveredMinimum

protected double findUncoveredMinimum()
Description copied from class: KuhnMunkresWong
Find the minimum in the uncovered rows.
Overrides:
findUncoveredMinimum in class KuhnMunkresWong
Returns:
Minimum in uncovered rows
• #### removeCost

protected void removeCost​(double h)
Description copied from class: KuhnMunkresWong
Remove cost h (if > 0) found to be unavoidable.
Overrides:
removeCost in class KuhnMunkresWong
Parameters:
h - Cost to remove