A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is -hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k=1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.     

Investigation of secondary flow and the related instability on an infinite yawed cylinder with Schubauer’s ellipse as section

This paper presents the principal results of a theoretical investigation of the secondary flow and the related instability performed in the laminar incompressible boundary layer on an infinite uniform yawed solid cylinder with Schubauer’s ellipse of axial ratio 2·96:1 as the section normal to the leading edge. The secondary flow profiles and the value of the instability criterion are obtained at different points of the wing section and for various angles of sweepback. It is found that in favourable pressure gradients and at pressure minimum, the secondary flow profiles have negative values. In regions of adverse pressure gradients after the pressure minimum the secondary flow changes sign from negative to positive values and have points of inflexion. The change of sign starts from the surface and extends to the edge of the boundary layer downstream. At some points in adverse pressure gradients the secondary flow profiles have double points of inflexion and values of both signs simultaneously. It is found that an adverse pressure gradient produces more powerful secondary flow than a favourable pressure gradient of the same strength. It is also found that the values of the instability criterion increase with the increasing sweepback whether the pressure gradient is favourable or adverse. At every point of the wing section, there are two values of the criterion for a given sweepback. The effect of adverse pressure gradient on the variation of the criterion is much more pronounced than that of a favourable pressure gradient. It is also seen that the flow is intermittently laminar and turbulent for low values of the chordwise free stream Reynolds number and for low values of sweepback and consists of an irregular sequence of laminar and turbulent regions.     

A remark on a standard and linear vector network equilibrium problem with capacity constraints

In this paper, (weak) vector equilibrium principle with capacity constraints is introduced. A necessary condition that a vector minimum cost flow is a vector equilibrium flow with capacity constraints is obtained. When the number of paths connecting with each pair of source and sink is less than or equal to 2, a sufficient condition for a vector minimum cost flow to be a vector equilibrium flow is also obtained. A generalized (weak) vector equilibrium principle is also introduced. Without any additional assumption, a necessary and sufficient condition for a (weak) vector minimum cost flow to be a generalized (weak) vector equilibrium flow is obtained.     

Sequential and parallel algorithms for minimum flows

First, we present two classes of sequential algorithms for minimum flow problem: decreasing path algorithms and preflow algorithms. Then we describe another approach of the minimum flow problem, that consists of applying any maximum flow algorithm in a modified network. In section 5 we present several parallel preflow algorithms that solve the minimum flow problem. Finally, we present an application of the minimum flow problem.     

A 3/2-Approximation for the proportionate two-machine flow shop scheduling with minimum delays

We study the two-machine flow shop problem with minimum delays. The problem is known to be strongly NP-hard even in the case of unit processing times and to be approximable within a factor of 2 of the length of an optimal schedule in the general case. The question whether there exists a polynomial-time algorithm with a better approximation ratio has been posed by several researchers but still remains open. In this paper, we improve the above bound to 3/2 for the special case of the problem when both operations of each job have equal processing times (this case of flow shop is known as the proportionate flow shop). Our analysis of the algorithm relies upon a nontrivial generalization of the lower bound established by W. Yu for the case of unit processing times.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

Optimizing flow rates in a queueing network with side constraints

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.     

Symplectic mean curvature flows in Kähler surfaces with positive holomorphic sectional curvatures

In this paper, we mainly study the mean curvature flow in Kähler surfaces with positive holomorphic sectional curvatures. We prove that if the ratio of the maximum and the minimum of the holomorphic sectional curvatures is less than $2$ , then there exists a positive constant $\delta $ depending on the ratio such that $\cos \alpha \ge \delta $ is preserved along the flow.     

会计数据的网络流分析

学者已证明一个会计主体如一家企业、其复式簿记中一级账户记录的数据组成一个矩阵;继而提出了会计回路概念,并认识到会计回路符合网络的某些规律.提出复式簿记系统的矩阵对应于1个网络,该网络存在着网络流.图论中的最大流最小割定理在该网络中同样有效,可以对之求解最大流最小割.最小割的集合是网络中的"瓶颈",直接影响着总的通过流量.计算出最小割的值,找出它由哪些会计分录组成、关联到哪些会计科目、流量是多少,这正是该会计主体运营中的薄弱环节.这是会计史上第一种整体地、定量地分析会计主体运营状况的数学方法.     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.     

Axisymmetric bodies of minimum drag in hypersonic flow

The problem of determining the longitudinal contour of a slender, axisymmetric body in hypersonic flow which has minimum drag is considered. The pressure distribution is assumed to be Newtonian, while the skin-friction distribution is for laminar flow and depends on body geometry. This investigation is conducted with the method of steepest descent, whose feasiblity is demonstrated by solving minimum drag problems having known analytical solutions.     

On the flow cost lowering problem

This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost on each arc by upgrading the arc. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series–parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series–parallel graphs.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

紧急网络中的最小饱和流问题

网络N中的一个流,如果沿前向已无法再增流,则称为饱和流,在交通拥挤或紧急疏散时,网络往往被一饱和流所堵塞。显然,这饱和流的值越小,网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。     

Flows on hypergraphs

We consider the capacitated minimum cost flow problem on directed hypergraphs. We define spanning hypertrees so generalizing the spanning tree of a standard graph, and show that, like in the standard and in the generalized minimum cost flow problems, a correspondence exists between bases and spanning hypertrees. Then, we show that, like for the network simplex algorithms for the standard and for the generalized minimum cost flow problems, most of the computations performed at each pivot operation have direct hypergraph interpretations.     

车身非光滑表面凹坑排布对气动性能的影响

受仿生学非光滑旋成体减阻启发,以SAE(美国机动车工程师协会)标准模型为研究对象,采用CFD(计算流体力学)数值模拟方法,在SAE模型顶部布置不同排布形式和不同排布密度的凹坑单元,研究其对车身气动性能的影响.通过比较各模型的尾流、气流速度、压力场、湍流动能等流场性能指标,分析非光滑表面减阻机理以及造成各模型流场性质差异的原因.计算结果显示:当凹坑型非光滑单元以矩形排布时模型具有最小的气动阻力,且气动阻力随着凹坑密度的增加而减小,减阻率最高达到4.1%.