Finding minimum-cost flows by double scaling

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.     

Three-dimensional transient thermoelectric currents in deep penetration laser welding of austenite stainless steel

The existence of thermoelectric currents (TECs) in workpieces during the laser welding of metals has been common knowledge for more than 15 years. However, the time-dependent evolutions of TECs in laser welding remain unclear. The present study developed a novel three-dimensional theoretical model of thermoelectric phenomena in the fiber laser welding of austenite stainless steel and used it to observe the time-dependent evolutions of TECs for the first time. Our model includes the complex physical effects of thermal, electromagnetic, fluid and phase transformation dynamics occurring at the millimeter laser ablated zone, which allowed us to simulate the TEC, self-induced magnetic field, Lorentz force, keyhole and weld pool behaviors varying with the welding time for different parameters. We found that TECs are truly three-dimensional, time-dependent, and uneven with a maximum current density of around 10⁷ A/m² located at the liquid-solid (L/S) interface near the front or bottom part of the keyhole at a laser power of 1.5 kW and a welding speed of 3 m/min. The TEC formed three-dimensional circulations moving from the melting front to solidification front in the solid part of workpiece, after which the contrary direction was followed in the liquid part. High frequency oscillation characteristics (2.2–8.5 kHz) were demonstrated in the TEC, which coincides with that of the keyhole instability (2.0–5.0 kHz). The magnitude of the self-induced magnetic field and Lorentz force can reach 0.1 mT and 1 kN/m³, respectively, which are both consistent with literature data. The predicted results of the weld dimensions by the proposed model agree well with the experimental results. Our findings could enhance the fundamental understanding of thermoelectric phenomena in laser welding.     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。