Suppose G = (S, T, E) is a bipartite graph, where (S,T) is a bipartiti
on of the vertex set. A beta-assignment is an edge set X subset of or
equal to E such that deg(X)(i) = 1 for all i is an element of S. The c
ardinality beta-assignment problem is to find a beta-assignment X whic
h minimizes beta(X) = max(j is an element of)T deg(X)(j). Suppose we a
ssociate every edge with a weight which is a real number. The bottlene
ck beta-assignment problem is to find a beta-assignment X that minimiz
es beta(X) and maximizes the minimum edge weight on X. The weighted be
ta-assignment problem is to find a beta-assignment X that minimizes be
ta(X) and maximizes the total weights of edges in X. This paper presen
ts O(/SJ//E/)-time algorithms for the cardinality and the bottleneck b
eta-assignment problems and an O(/S/(2)/T/ + /S//T/(2))-time algorithm
for the weighted beta-assignment problem. (C) 1998 Elsevier Science B
.V.