We consider the problem of fairly matching the left-hand vertices of
a bipartite graph to the right-hand vertices.
We refer to this problem as the \em{semi-matching} problem; 
it is a relaxation of the known bipartite matching problem.
We present a way to evaluate the quality of a given semi-matching and show
that, under this measure, an optimal semi-matching balances the load on the
right hand vertices with respect to any $L_p$-norm. In particular,
when modeling a job assignment system, an optimal semi-matching
achieves the minimal makespan and the minimal flow time for the system.

The problem of finding optimal semi-matchings is a special case of certain
scheduling problems for which known solutions exist. 
However, these known solutions are based on general network optimization
algorithms, and are not the most efficient way to solve the optimal
semi-matching problem.  
To compute optimal semi-matchings efficiently, we present and analyze two
new algorithms. The first algorithm generalizes the Hungarian 
method for computing maximum bipartite matchings, while the second, more
efficient algorithm is based on a new notion of \em{cost-reducing paths}. 
Our experimental results demonstrate that the second algorithm is vastly
superior to using known network optimization algorithms to solve the
optimal semi-matching problem. 
Furthermore, this same algorithm can also be used to find maximum bipartite
matchings and is shown to be roughly as efficient as the best known algorithms for this goal.