On the history of the transportation and maximum flow problems

We review two papers that are of historical interest for combinatorial optimization: an article of A.N. Tolsto&ıbreve; from 1930, in which the transportation problem is studied, and a negative cycle criterion is developed and applied to solve a (for that time) large-scale (10×68) transportation problem to optimality; and an, until recently secret, RAND report of T.E. Harris and F.S. Ross from 1955, that Ford and Fulkerson mention as motivation to study the maximum flow problem. The papers have in common that they both apply their methods to the Soviet railway network. Received: August 11, 2000 / Accepted: March 28, 2001?Published online October 26, 2001     

Orbits of the geodesic flow and chains on the boundary of a Grauert tube

A Riemannian manifold (X,g) determines an integrable complex structure on a tubular neighborhood, , of the zero section in and a CR-structure on the boundary, . There are two natural families of curves on : the orbits of the geodesic flow and a CR-invariant family called chains. It is natural to ask whether they are related. We show that if orbits of the geodesic flow are chains on for all sufficiently small, then (X,g) is Einstein. As a partial converse we show that if (X,g) is harmonic, then orbits of the geodesic flow are chains. To prove this we study the Fefferman metric associated with . Received: 1 April 1998 / Revised version: 25 May 2001 / Published online: 19 October 2001     

Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

Rapid time-decay and net force to the obstacles by the Stokes flow in exterior domains

Consider the nonstationary Stokes equations in exterior domains with the compact boundary . We show first that the solution decays like for all as . This decay rate is optimal in the sense that for some as occurs if and only if the net force exerted by the fluid on is zero. Received: 15 June 2000 / Published online: 18 June 2001     

A remark on the finite time singularity of the heat flow for harmonic maps

In this paper we study the finite time singularities for the solution of the heat flow for harmonic maps. We derive a gradient estimate for the solution across a finite time singularity. In particular, we find that the solution is asymptotically radial around the isolated singular point in space at a finite singular time. It would be more desirable to understand whether the solution is continuous in space at a finite singular time.Received: 15 March 2001, Accepted: 16 June 2002, Published online: 17 December 2002     

Ricci flow on Kähler-Einstein surfaces

In this paper, we prove that if M is a K?hler-Einstein surface with positive scalar curvature, if the initial metric has nonnegative sectional curvature, and the curvature is positive somewhere, then the K?hler-Ricci flow converges to a K?hler-Einstein metric with constant bisectional curvature. In a subsequent paper [7], we prove the same result for general K?hler-Einstein manifolds in all dimension. This gives an affirmative answer to a long standing problem in K?hler Ricci flow: On a compact K?hler-Einstein manifold, does the K?hler-Ricci flow converge to a K?hler-Einstein metric if the initial metric has a positive bisectional curvature? Our main method is to find a set of new functionals which are essentially decreasing under the K?hler Ricci flow while they have uniform lower bounds. This property gives the crucial estimate we need to tackle this problem. Oblatum 8-IX-2000 & 30-VII-2001?Published online: 19 November 2001     

Regularity for the approximated harmonic map equation and application to the heat flow for harmonic maps

Let be open and a smooth, compact Riemannian manifold without boundary. We consider the approximated harmonic map equation for maps , where . For , we prove H?lder continuity for weak solution s which satisfy a certain smallness condition. For , we derive an energy estimate which allows to prove partial regularity for stationary solutions of the heat flow for harmonic maps in dimension . Received: 7 May 2001; / in final form: 22 February 2002 Published online: 2 December 2002     

Fast and simple approximation schemes for generalized flow

We present fast and simple fully polynomial-time approximation schemes (FPTAS) for generalized versions of maximum flow, multicommodity flow, minimum cost maximum flow, and minimum cost multicommodity flow. We extend and refine fractional packing frameworks introduced in FPTAS’s for traditional multicommodity flow and packing linear programs. Our FPTAS’s dominate the previous best known complexity bounds for all of these problems, some by more than a factor of n ², where n is the number of nodes. This is accomplished in part by introducing an efficient method of solving a sequence of generalized shortest path problems. Our generalized multicommodity FPTAS’s are now as fast as the best non-generalized ones. We believe our improvements make it practical to solve generalized multicommodity flow problems via combinatorial methods. Received: June 3, 1999 / Accepted: May 22, 2001?Published online September 17, 2001     

Angle theorems for the Lagrangian mean curvature flow

We prove that symplectic maps between Riemann surfaces L, M of constant, nonpositive and equal curvature converge to minimal symplectic maps, if the Lagrangian angle for the corresponding Lagrangian submanifold in the cross product space satisfies . If one considers a 4-dimensional K?hler-Einstein manifold of nonpositive scalar curvature that admits two complex structures J, K which commute and assumes that is a compact oriented Lagrangian submanifold w.r.t. J such that the K?hler form w.r.t.K restricted to L is positive and , then L converges under the mean curvature flow to a minimal Lagrangian submanifold which is calibrated w.r.t. . Received: 11 April 2001 / Published online: 29 April 2002     

A stochastic selection principle in case of fattening for curvature flow

Consider two disjoint circles moving by mean curvature plus a forcing term which makes them touch with zero velocity. It is known that the generalized solution in the viscosity sense ceases to be a curve after the touching (the so-called fattening phenomenon). We show that after adding a small stochastic forcing , in the limit the measure selects two evolving curves, the upper and lower barrier in the sense of De Giorgi. Further we show partial results for nonzero . Received: 3 November 2000 / Accepted: 4 December 2000 / Published online: 23 April 2001     

Robustness in a posteriori error analysis for FEM flow models

Summary. We derive a residual-based a posteriori error estimator for a stabilized finite element discretization of certain incompressible Oseen-like equations. We focus our attention on the behaviour of the effectivity index and we carry on a numerical study of its sensitiveness to the problem and mesh parameters. We also consider a scalar reaction-convection-diffusion problem and a divergence-free projection problem in order to investigate the effects on the robustness of our a posteriori error estimator of the reaction-convection-diffusion phenomena and, separately, of the incompressibility constraint. Received March 21, 2001 / Revised version received July 30, 2001 / Published online October 17, 2001     

A splitting positive definite mixed element method for miscible displacement of compressible flow in porous media

A miscible displacement of one compressible fluid by another in a porous medium is governed by a nonlinear parabolic system. A new mixed finite element method, in which the mixed element system is symmetric positive definite and the flux equation is separated from pressure equation, is introduced to solve the pressure equation of parabolic type, and a standard Galerkin method is used to treat the convection‐diffusion equation of concentration of one of the fluids. The convergence of the approximate solution with an optimal accuracy in L²‐norm is proved. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 229–249, 2001     

Convergence acceleration by varying time‐step size using Bi‐CGSTAB method for turbulent flow computation

A design of varying step size approach both in time span and spatial coordinate systems to achieve fast convergence is demonstrated in this study. This method is based on the concept of minimization of residuals by the Bi‐CGSTAB algorithm, so that the convergence can be enforced by varying the time‐step size. The numerical results show that the time‐step size determined by the proposed method improves the convergence rate for turbulent computations using advanced turbulence models in low Reynolds‐number form, and the degree of improvement increases with the degree of the complexity of the turbulence models. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 454–474, 2001.     

Long-time existence and convergence of graphic mean curvature flow in arbitrary codimension

Let f:Σ₁↦Σ₂ be a map between compact Riemannian manifolds of constant curvature. This article considers the evolution of the graph of f in Σ₁×Σ₂ by the mean curvature flow. Under suitable conditions on the curvature of Σ₁ and Σ₂ and the differential of the initial map, we show that the flow exists smoothly for all time. At each instant t, the flow remains the graph of a map f _t and f _t converges to a constant map as t approaches infinity. This also provides a regularity estimate for Lipschitz initial data. Oblatum 30-I-2001 & 24-X-2001?Published online: 1 February 2002     

A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

History of mathematical programming in the USSR: analyzing the phenomenon

I am not a historian; these are just reminiscences of a person involved in the development of optimization theory and methods in the former USSR. I realize that my point of view may be very personal; however, I am trying to present as broad and unbiased picture as I can. Received: January 29, 2001 / Accepted: May 17, 2001?Published online October 2, 2001     

Combinatorial interior point methods for generalized network flow problems

 We present combinatorial interior point methods for the generalized minimum cost flow and the generalized circulation problems based on Wallacher and Zimmermann's combinatorial interior point method for the minimum cost network flow problem. The algorithms have features of both a combinatorial algorithm and an interior point method. They work towards optimality by iteratively reducing the value of a potential function while maintaining interior point solutions. At each iteration, flow is augmented along a generalized circulation, which is computed by solving a TVPI (Two Variables Per Inequality) system. The algorithms run in time, where m and n are, respectively, the number of arcs and nodes in the graph, and L is the length of the input data. Received: June 1, 2001 / Accepted: May 23, 2002-08-22 Published online: September 27, 2002 RID="*" ID="*" This research was supported in part by NSF Grants DMS 94-14438, DMS 95-27124, CDA 97-26385 and DMS 01-04282, and DOE Grant DE-FG02-92ER25126 Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Real flow number and the cycle rank of a graph

This article establishes a relationship between the real (circular) flow number of a graph and its cycle rank. We show that a connected graph with real flow number p/q + 1, where p and q are two relatively prime numbers must have cycle rank at least p + q ? 1. A special case of this result yields that the real flow number of a 2‐connected cubic graph with chromatic index 4 and order at most 8k + 4 is bounded from below by 4 + 1/k. Using this bound we prove that the real flow number of the Isaacs snark I_{2k + 1} equals 4 + 1/k, completing the upper bound due to Steffen [Steffen, J Graph Theory 36 (2001), 24–34]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 11–16, 2008