MONGE MATRICES MAKE MAXIMIZATION MANAGEABLE

We continue the research on the effects of Monge structures in the are a of combinatorial optimization. We show that three optimization probl ems become easy if the underlying cost matrix fulfills the Monge prope rty: (A) The balanced max-cut problem, (B) the problem of computing mi nimum weight binary k-matchings and (C) the computation of longest pat hs in bipartite, edge-weighted graphs. In all three results, we first prove that the Monge structure imposes some special combinatorial prop erty on the structure of the optimum solution, and then we exploit thi s combinatorial property to derive efficient algorithms.