We consider one variant of stable assignment problems in a bipartite graph endowed with nonnegative capacities on the edges and quotas on the vertices. It can be viewed as a generalization of the stable allocation problem introduced by Baïou and Balinsky, which arises when strong linear orders of preferences on the vertices in the latter are replaced by weak ones. At the same time, our stability problem can be stated in the framework of a theory by Alkan and Gale on stable schedule matchings generated by choice functions of a wide scope. In our case, the choice functions are of a special, so-called mixed , type. The main content of this paper is devoted to a study of rotations in our mixed model, functions on the edges determining “elementary” transformations between close stable assignments. These look more sophisticated compared with rotations in the stable allocation problem (which are generated by simple cycles). We efficiently construct a poset of rotations and show that the stable assignments are in bijection with the so-called closed functions for this poset; this gives rise to a “compact” affine representation for the lattice of stable assignments and leads to an efficient method to find a stable assignment of minimum cost.

We consider the problem of minimizing a separable convex objective function over the linear space given by a system Mx=0 with M a totally unimodular matrix. In particular, this generalizes the usual minimum linear cost circulation and cocirculation problems in a network and the problems of determining the Euclidean distance from a point to the perfect bipartite matching polytope and the feasible flows polyhedron. We first show that the idea of minimum mean cycle canceling originally worked out for linear cost circulations by Goldberg and Tarjan [J. Assoc. Comput. Mach., 36 (1989), pp. 873--886.] and extended to some other problems [T. R. Ervolina and S. T. McCormick, Discrete Appl. Math., 46 (1993), pp. 133--165], [A. Frank and A. V. Karzanov, Technical Report RR 895-M, Laboratoire ARTEMIS IMAG, Université Joseph Fourier, Grenoble, France, 1992], [T. Ibaraki, A. V. Karzanov, and H. Nagamochi, private communication, 1993], [M. Hadjiat, Technical Report, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Marseille, France, 1994] can be generalized to give a combinatorial method with geometric convergence for our problem. We also generalize the computationally more efficient cancel-and-tighten method. We then consider objective functions that are piecewise linear, pure and piecewise quadratic, or piecewise mixed linear and quadratic, and we show how both methods can be implemented to find exact solutions in polynomial time (strongly polynomial in the piecewise linear case). These implementations are then further specialized for finding circulations and cocirculations in a network. We finish by showing how to extend our methods to find optimal integer solutions, to linear spaces of larger fractionality, and to the case when the objective functions are given by approximate oracles.

Generalizing the two-commodity flow theorem of Rothschild and Whinston [Oper. Res., 14 (1966), pp. 377--387] and the multiflow theorem of Lovász [Acta Mat. Akad. Sci. Hungaricae, 28 (1976), pp. 129--138] and Cherkasky [Ekonom.-Mat. Metody, 13 (1977), pp. 143--151], Karzanov and Lomonosov [Mathematical Programming, O. I. Larichev, ed., Institute for System Studies, 1978, pp. 59--66] in 1978 proved a min-max theorem on maximum multiflows. Their original proof is quite long and technical and relies on earlier investigations into metrics. The main purpose of the present paper is to provide a relatively simple proof of this theorem. Our proof relies on the locking theorem, which is another result of Karzanov and Lomonosov, and the polymatroid intersection theorem of Edmonds [Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, 1970, pp. 69--87]. For completeness, we also provide a simplified proof of the locking theorem. Finally, we introduce the notion of a node demand problem and, as another application of the locking theorem, we derive a feasibility theorem concerning it. The presented approach gives rise to (combinatorial) polynomial-time algorithms.