Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

用于光学神经网络硬件系统误差纠正的虚拟神经网络

提出了一种用于修正光学神经网络硬件系统误差的虚拟神经网络模型，光学实验结果表明该网络能够有效地消除硬件系统误差对实验结果的影响。     

IPv4/IPv6翻译网关的研究

In this paper, a model of translation gateway is proposed. The communications between IPv4 network and IPv6 network are realized by using the Microsoft intermediate driver technology in environment of Windows 2000.     

Stability criteria for controlled queueing systems

We give an almost complete classification of ergodicity and transience conditions for a general multi-queue system with the following features: arrivals form Poisson streams and there are various routing schemes for allocating arrivals to queues; the servers can be configured in a variety of ways; completed jobs can feed back into the system; the exponential service times and feedback probabilities depend upon the configuration of the servers (this model includes some types of multi-class queueing system); switching between service regimes is instantaneous. Several different levels of control of the service regimes are considered. Our results for the N-queue system require randomisation of service configurations but we have studied the two queue system in situations where there is less control. We use the semi-martingale methods described in Fayolle, Malyshev and Menshikov [3] and our results generalise Kurkova [8] and complement Foley and McDonald [4] and [5]. AMS 2000 subject classification: Primary: 90B22; Secondary: 60J10 90B15     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

Electro-optical performance of polymer stabilized cholesteric texture cell: The influence of chiral dopant and monomer concentration

Reverse-mode polymer stabilized cholesteric texture (PSCT) cells with various chiral dopant and monomer concentrations were fabricated. Experimental results indicate that the chiral dopant concentration and the monomer concentration significantly influence the threshold voltage and hysteresis of the cells. The chiral dopant and monomer deform the hysteresis loop. Increasing the monomer concentration reduces the width of the hysteresis loop of the reverse-mode PSCT cell.     

Boiling heat transfer characteristics of nanofluids in a flat heat pipe evaporator with micro-grooved heating surface

An experimental study was performed to understand the nucleate boiling heat transfer of water–CuO nanoparticles suspension (nanofluids) at different operating pressures and different nanoparticle mass concentrations. The experimental apparatus is a miniature flat heat pipe (MFHP) with micro-grooved heat transfer surface of its evaporator. The experimental results indicate that the operating pressure has great influence on the nucleate boiling characteristics in the MFHP evaporator. The heat transfer coefficient and the critical heat flux (CHF) of nanofluids increase greatly with decreasing pressure as compared with those of water. The heat transfer coefficient and the CHF of nanofluids can increase about 25% and 50%, respectively, at atmospheric pressure whereas about 100% and 150%, respectively, at the pressure of 7.4 kPa. Nanoparticle mass concentration also has significant influence on the boiling heat transfer and the CHF of nanofluids. The heat transfer coefficient and the CHF increase slowly with the increase of the nanoparticle mass concentration at low concentration conditions. However, when the nanoparticle mass concentration is over 1.0 wt%, the CHF enhancement is close to a constant number and the heat transfer coefficient deteriorates. There exists an optimum mass concentration for nanofluids which corresponds to the maximum heat transfer enhancement and this optimum mass concentration is 1.0 wt% at all test pressures. The experiment confirmed that the boiling heat transfer characteristics of the MFHP evaporator can evidently be strengthened by using water/CuO nanofluids.     

Circuit-switching networks with FIFO plus justifying blockout service on infinite graphs

A class of circuit-switching open queueing networks is discussed. The main result of the paper is that if extra message flows are not too intensive and the path distribution is mainly concentrated on the paths of (graph) distance 1 (nearest neighbour connections), then the network has a unique stationary working regime, no matter how large the configuration graph of the network is. Standard properties of this regime are established such as decay of correlation and continuity.     

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

Minimum concave cost production system: A further generalization of multi-echelon model

We will consider a concave minimization problem associated with a series production system in which raw material is processed inm consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during periodi, i = 1,,n, are known in advance. Our problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave.The origin of this model is the classical economic lot size problem of Wagner and Whitin and was extensively studied by Zangwill. This model is very important from the theoretical as well as practical point of view and this is one of the very rare instances in which polynomial time algorithm has been constructed for concave minimization problems.The purpose of this paper is to extend the model further to the situation in which time lag is associated with processing at each facility. We will propose an efficient O(n ⁴ m) algorithm for this class of problems.