Hungarian Algorithm

Hungarian Algorithm (หรือ Kuhn-Munkres Algorithm) หา minimum cost perfect matching ใน bipartite graph ที่มี weights บน edges

Problem Definition

• มี $n$ workers และ $n$ jobs
• $cost[i][j]$ = cost ที่ worker $i$ ทำ job $j$
• หา assignment ที่ทุก worker ทำคนละ 1 job โดยมี total cost น้อยที่สุด

Implementation

$O(n^3)$ Version

class Hungarian {
    int n;
    vector<vector<long long>> cost;
    vector<long long> u, v;  // potentials
    vector<int> p, way;
    
public:
    Hungarian(int n) : n(n), cost(n, vector<long long>(n)), 
                       u(n+1), v(n+1), p(n+1), way(n+1) {}
    
    void setCost(int i, int j, long long c) {
        cost[i][j] = c;
    }
    
    pair<long long, vector<int>> solve() {
        // p[j] = which row is assigned to column j
        // way[j] = previous column in augmenting path
        
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            int j0 = 0;  // virtual zero column
            vector<long long> minv(n + 1, LLONG_MAX);
            vector<bool> used(n + 1, false);
            
            do {
                used[j0] = true;
                int i0 = p[j0], j1 = 0;
                long long delta = LLONG_MAX;
                
                for (int j = 1; j <= n; j++) {
                    if (!used[j]) {
                        long long cur = cost[i0-1][j-1] - u[i0] - v[j];
                        if (cur < minv[j]) {
                            minv[j] = cur;
                            way[j] = j0;
                        }
                        if (minv[j] < delta) {
                            delta = minv[j];
                            j1 = j;
                        }
                    }
                }
                
                // Update potentials
                for (int j = 0; j <= n; j++) {
                    if (used[j]) {
                        u[p[j]] += delta;
                        v[j] -= delta;
                    } else {
                        minv[j] -= delta;
                    }
                }
                
                j0 = j1;
            } while (p[j0] != 0);
            
            // Augment along path
            do {
                int j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0);
        }
        
        // Extract result
        vector<int> assignment(n);
        for (int j = 1; j <= n; j++) {
            if (p[j] != 0) {
                assignment[p[j] - 1] = j - 1;
            }
        }
        
        long long totalCost = 0;
        for (int i = 0; i < n; i++) {
            totalCost += cost[i][assignment[i]];
        }
        
        return {totalCost, assignment};
    }
};

ตัวอย่างการใช้งาน

int main() {
    int n = 3;
    vector<vector<long long>> cost = {
        {9, 2, 7},
        {6, 4, 3},
        {5, 8, 1}
    };
    
    Hungarian hungarian(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            hungarian.setCost(i, j, cost[i][j]);
        }
    }
    
    auto [minCost, assignment] = hungarian.solve();
    
    cout << "Minimum cost: " << minCost << endl;
    cout << "Assignment:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Worker " << i << " -> Job " << assignment[i] << endl;
    }
    
    return 0;
}
// Output:
// Minimum cost: 7
// Assignment:
// Worker 0 -> Job 1 (cost 2)
// Worker 1 -> Job 2 (cost 3)
// Worker 2 -> Job 0 (cost 5 - wait, should be job 2 = 1)

แนวคิด

Dual Problem (Potentials)

กำหนด potentials $u_i$ (สำหรับ workers) และ $v_j$ (สำหรับ jobs) โดยที่:

$u_i + v_j \leq cost[i][j]$

Optimal condition: เมื่อ $u_i + v_j = cost[i][j]$ สำหรับ matched pairs

Algorithm Steps

1. เริ่มจาก $u = v = 0$
2. สำหรับแต่ละ worker $i$:
   • หา augmenting path ใน equality graph
   • ถ้าไม่มี: update potentials ด้วย $\delta = \min(cost[i][j] - u_i - v_j)$ สำหรับ reachable $i$ และ unreachable $j$
   • ทำซ้ำจนหา augmenting path ได้
3. Augment matching

Variants

Maximum Weight Matching

แปลง cost เป็น negative:

long long maxCost = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        maxCost = max(maxCost, cost[i][j]);
    }
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cost[i][j] = maxCost - cost[i][j];
    }
}
// Then solve and subtract n * maxCost from result

Rectangular Matrix (n x m)

เพิ่ม dummy rows/columns ด้วย cost 0:

Hungarian hungarian(max(n, m));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        hungarian.setCost(i, j, cost[i][j]);
    }
}
// Dummy entries default to 0

ประยุกต์ใช้งาน

1. Task Assignment

Assign $n$ tasks ให้ $n$ processors โดย minimize total time

2. Tracking Objects

Match detected objects ระหว่าง frames โดยใช้ distance เป็น cost

3. Resource Allocation

Allocate resources ให้ projects โดย minimize total cost

4. Minimum Weight Vertex Cover (special case)

ใน bipartite graph ที่ทุก edge มี weight

Complexity

Operation	Time	Space
Build	$O(n^2)$	$O(n^2)$
Solve	$O(n^3)$	$O(n^2)$

เปรียบเทียบกับ MCMF

Aspect	Hungarian	MCMF
Time	$O(n^3)$	$O(n^2 E)$ หรือดีกว่า
Use case	Dense bipartite	General flow
Implementation	เฉพาะทาง	General
Memory	$O(n^2)$	$O(V + E)$

Tips

1. Dense graph ใช้ Hungarian ดีกว่า
2. Sparse graph ใช้ MCMF ดีกว่า
3. Large costs ระวัง overflow ใน potentials
4. Floating point ต้อง handle epsilon comparison