The β-assignment problems

Suppose G = (S, T, E) is a bipartite graph, where (S, T) is a bipartition of the vertex set. A β-assignment is an edge set X ⊆ E such that degX(i) = 1 for all i ∈ S. The cardinality β-assignment problem is to find a β-assignment X which minimizes β(X) = maxj∈T degX(j). Suppose we associate every edge with a weight which is a real number. The bottleneck β-assignment problem is to find a β-assignment X that minimizes β(X) and maximizes the minimum edge weight on X. The weighted β-assignment problem is to find a β-assignment X that minimizes β(X) and maximizes the total weights of edges in X. This paper presents O(|S||E|)-time algorithms for the cardinality and the bottleneck β-assignment problems and an O(|S|²|T| + |S||T|²)-time algorithm for the weighted β-assignment problem.