# Two exact algorithms for the generalized assignment problem

arXiv: https://arxiv.org/abs/1303.4031 · HTML: https://mlsanity.com/paper/1303.4031/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2013.

## Built on by (most cited first, 1 of 1)

- [Many-to-Many Matching via Sparsity Controlled Optimal Transport](https://mlsanity.com/paper/2503.24204/) (2025)

## Abstract (arXiv)

Let A={a_1,a_2,...,a_s} and B={b_1,b_2,...,b_t} be two sets of objects with s+r=n, the generalized assignment problem assigns each element a_i in A to at least alpha_i and at most alpha '_i elements in B, and each element b_j in B to at least beta_j and at most beta '_j elements in A for all 1 <= i <= s and 1 <= j <= t. In this paper, we present an O(n^4) time and O(n) space algorithm for this problem using the well known Hungarian algorithm. We also present an O(n^3) algorithm for a special case of the generalized assignment, called the limited-capacity assignment problem, where alpha_i,beta_j=1 for all i,j.