FastHungarian

Fast assignment problem solver based on modified Kwok's algorithm for maximum weight matching on bipartite graphs. Supports anything from .NET Standard 2.0 to modern .NET 10+ with no dependencies. Solves both minimum cost assignment (Hungarian algorithm) and maximum weight matching problems. This solver achieves 2.5x speed up on dense 10x10 matrices and over 80 times speed up on sparse 100x100 materies, compared with HungarianAlgorithm while maintaining optimal solutions. Extensively tested with comprehensive fuzz testing across thousands of matrix configurations.

Install the package via NuGet:

dotnet add package FastHungarian

Solve assignment problems:

using FastHungarian;

// Cost matrix: assign workers to tasks minimizing total cost
int[,] costs = new int[,]
{
    { 10, 25, 15, 20 },  // Worker 0 costs for tasks 0-3
    { 15, 30, 5,  15 },  // Worker 1 costs for tasks 0-3
    { 20, 5,  10, 25 },  // Worker 2 costs for tasks 0-3
    { 25, 20, 15, 10 }   // Worker 3 costs for tasks 0-3
};

int[] assignments = FastHungarian.FindAssignments(costs);
// assignments[i] = task assigned to worker i
// Result: [2, 2, 1, 3] means Worker 0→Task 2, Worker 1→Task 2, etc.

⭐ That's it! The algorithm automatically handles:

• Non-square matrices (different number of workers and tasks)
• Transposition for optimal performance
• Edge retention optimization for large graphs

Matching result = FastHungarian.FindAssignmentsWithWeight(costs);
Console.WriteLine($"Optimal cost: {result.WeightSum}");
Console.WriteLine($"Assignments: {string.Join(", ", result.LeftPairs)}");

For sparse graphs or when you want to maximize weights instead of minimize costs:

// Bipartite graph: L = {0, 1, 2}, R = {0, 1, 2, 3}
// Each list contains (vertex, weight) pairs
var adjacencyList = new List<List<(int vertex, int weight)>>
{
    [(0, 10), (1, 5), (2, 3)],     // Vertex 0 edges
    [(1, 8), (2, 7), (3, 9)],      // Vertex 1 edges
    [(0, 4), (2, 12), (3, 6)]      // Vertex 2 edges
};

Matching result = FastHungarian.MaximumWeightMatching(
    leftCount: 3, 
    rightCount: 4, 
    adjacencyList
);

Console.WriteLine($"Maximum weight: {result.WeightSum}");
// result.LeftPairs[i] = matched right vertex for left vertex i
// result.RightPairs[j] = matched left vertex for right vertex j

// More workers than tasks: some workers won't be assigned
int[,] costs = new int[5, 3];  // 5 workers, 3 tasks
int[] assignments = FastHungarian.FindAssignments(costs);
// assignments.Length == 5
// assignments[i] == -1 if worker i is not assigned

// More tasks than workers: all workers assigned, some tasks unassigned
int[,] costs2 = new int[3, 5];  // 3 workers, 5 tasks
int[] assignments2 = FastHungarian.FindAssignments(costs2);
// assignments2.Length == 3
// All assignments2[i] >= 0

FastHungarian implements modified Kwok's 2025 algorithm for maximum weight matching with several optimizations:

1. Flat adjacency list - Better cache locality vs nested lists
2. Edge retention (Theorem 4.2.1) - Reduces edges to O(|L|) per vertex using QuickSelect
3. Pre-computed labels - Eliminates redundant scans
4. Incremental slack tracking - Avoids repeated minimum calculations
5. Ring buffer BFS - Reduces queue overhead
6. Span bounds check elimination (.NET 8+) - Zero-overhead array access
7. Branchless operations - Better CPU pipelining

• Time: O(|L| × |R| × min(|L|, |R|)) worst case, typically much faster in practice
• Space: O(|L| × min(|L|, |R|)) due to edge retention
• Classical Hungarian: O(|L|³) or O(|L|² × |R|)

Benchmark results on Intel Core i7-8700 (Coffee Lake), baseline (referred to as "vanilla") implementation is available here:

Full benchmark results and reproduction available in the benchmark project.

FastHungarian is thoroughly tested with 11 comprehensive fuzz test suites covering:

• ✅ Square matrices (2×2 to 200×200)
• ✅ Non-square matrices (all aspect ratios)
• ✅ Extreme shapes (1×N, N×1, 10:1 ratios)
• ✅ Edge case patterns (diagonal, sparse, bimodal, outliers)
• ✅ Degenerate cases (1×1, single row/column, near-overflow)
• ✅ Total: 350+ test iterations, thousands of matrix configurations

All tests verify correctness against the proven Hungarian algorithm implementation from the HungarianAlgorithm NuGet package.

• Integer weights: Currently supports int weights. For floating-point weights, scale to integers.

The algorithm handles:

• ✅ Non-square matrices (automatic transposition)
• ✅ Unbalanced assignments (more workers than tasks or vice versa)
• ✅ Zero costs and identical values
• ✅ Large cost ranges (tested up to int.MaxValue / 2)

If you are looking to add new functionality, please open an issue first to verify your intent is aligned with the scope of the project. The library is covered by comprehensive fuzz tests with over 350 test iterations. Please run them against your work before proposing changes:

dotnet test

When reporting issues, providing a minimal reproduction with the specific cost matrix that fails greatly reduces turnaround time.

• Kwok, J. T. (2025). An Improved Algorithm for Maximum Weight Matching in Bipartite Graphs
• Based on the classical Hungarian algorithm (Kuhn-Munkres algorithm)

This library is licensed under the MIT license. 💜