Av. Karzanov et St. Mccormick, POLYNOMIAL METHODS FOR SEPARABLE CONVEX-OPTIMIZATION IN UNIMODULAR LINEAR-SPACES WITH APPLICATIONS, SIAM journal on computing, 26(4), 1997, pp. 1245-1275
Citations number
32
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
We consider the problem of minimizing a separable convex objective fun
ction over the linear space given by a system Mt = a with M a totally
unimodular matrix. In particular, this generalizes the usual minimum l
inear cost circulation and cocirculation problems in a network and the
problems of determining the Euclidean distance from a point to the pe
rfect bipartite matching polytope and the feasible flows polyhedron. W
e first show that the idea of minimum mean cycle canceling originally
worked out for linear cost circulations by Goldberg and Tarjan [J. Ass
oc. 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, Universite Joseph Fourier, Grenobl
e, France, 1992], [T. Ibaraki, A. V. Karzanov, and H. Nagamochi, priva
te communication, 1993], [M. Hadjiat, Technical Report, Groupe Intelli
gence Artificielle, Faculte des Sciences de Luminy, Marseille, France,
1994] can be generalized to give a combinatorial method with geometri
c convergence for our problem. We also generalize the computationally
more efficient cancel-and-tighten method. We then consider objective f
unctions that are piecewise linear, pure and piecewise quadratic, or p
iecewise mixed linear and quadratic, and we show how both methods can
be implemented to find exact solutions in polynomial time (strongly po
lynomial 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 optima
l integer solutions, to linear spaces of larger fractionality, and to
the case when the objective functions are given by approximate oracles
.