Minimum cost multiflows in undirected networks

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena 0). Lovász and Cherkassky independently proved that the latter has a half-integral optimal solution.A pseudo-polynomial algorithm for solving (*) has been developed earlier and, as its consequence, the theorem on the existence of a half-integral optimal solution for (*) was obtained. In the present paper we give a direct, shorter, proof of this theorem. Then we prove the existence of a half-integral optimal solution for the dual problem. Finally, we show that half-integral optimal primal and dual solutions can be designed by a combinatorial strongly polynomial algorithm, provided that some optimal dual solution is known (the latter can be found, in strongly polynomial time, by use of a version of the ellipsoid method).This work was partially supported by Chaire municipale, Mairie de Grenoble, France.     

The asymptotic behavior of queueing systems: Large deviations theory and dominant pole approximation

This paper presents the exact asymptotics of the steady state behavior of a broad class of single-node queueing systems. First we show that the asymptotic probability functions derived using large deviations theory are consistent (in a certain sense) with the result using dominant pole approximations. Then we present an exact asymptotic formula for the cumulative probability function of the queue occupancy and relate it to the cell loss ratio, an important performance measure for service systems such as ATM networks. The analysis relies on a new generalization of the Taylor coefficients of a complex function which we call characteristic coefficients. Finally we apply our framework to obtain new results for the M/D/1 system and for a more intricate multiclass M/D/n system.     

局域网的规划与INTERNET的连接技术

介绍了NETWARE局域网的规划方法、实施步骤,并简述了其与INTERNET实现连接的几种方法。     

ATM广域网预测式流量控制方案

针对ＡＴＭ广域网的长时延特点,提出了一种预测式流量控制方案,通过预测各交换节点非受控业务流所占用的带宽,对各链路可获得带宽进行预测式分配;预测式方案结合本文作者提出的集中式流量控制机制,保证了带宽分配的公平性和链路利用的高效性;本文还在ＶＢＲ＋ＡＢＲ业务综合传输的情形下,进行了预测式流量控制方案的计算机仿真,仿真结果表明,本文的预测式算法具有带宽分配的公平性和链路利用的高效性,交换节点处缓冲队列很     

计算机网络技术的近期发展

目的 论述和分析计算机网络技术的近期发展。方法 通过分析交换技术,路由技术,第３层交换技术,实时信息传输技术和异步传输模式（ＡＴＭ）技术的特点,揭示各项网络技术适用面。结果 指出交换技术解决带宽问题,第３层交换技术解决路由瓶颈问题,ＡＴＭ等技术解雇实时信息传送问题。结论各项网技术都是针对某些实际需要提出的,都有其适用范围,用户选择时要从需求出发才能充分发挥网络的作用。     

高速网络业务模型及数据流量反馈控制研究

分析了高速通信网络不同业务类型的特点．根据不同业务对网络服务质量（ＱＯＳ）的要求及动态占用带宽的优先度,将其分为两种类型：一类业务可在预定的范围改变其传输速率,另一类是被动的,网络根据可用带宽的大小动态地调节其传输速率．文中给出了一种业务流量控制模型,该模型把带宽的高效率利用归结为如何对被动业务流量进行控制．按充分利用信道容量的原则,提出了一种自适应反馈控制算法．模拟表明,这种控制方法有良好的性能．     

Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

Network theory of the nonlinear behaviour of polymer melts. Simple shear flow

Summary The network model developed in a previous paper is applied to the simple shear flow of polymer melts. The constitutive equation obtained consists of two terms. One of them describes the stress due to the network strands which exist at the onset of the deformation, dissociate during the deformation and result in a single integral constitutive equation with a strain dependent damping function. The formulation of the damping function in invariant form seems to be almost impossible.The second normal stress differenceN ₂ of the model is not zero,but has negative values. According to our model this is a consequence of the deformation dependence of the disentanglement process. The theory is compared with experimental data for a LDPE melt. It is found that the model explains the main features of the shear flow behaviour of the LDPE melt investigated preciously.

---

Zusammenfassung Das Netzwerk-Modell, das in einer vorangegangenen Arbeit entwickelt wurde, wird für die einfache Scherströmung von Polymerschelzen angewendet. Die abgeleitete rheologische Zustandsgleichung besteht aus zwei Gliedern. Das erste beschreibt die Spannung-Dehnung-Beziehung der Kettensegmente, die zu Beginn der Deformation existieren und während der Deformation aufgelöst werden. Es hat die Form der einfachen Integralbeziehung mit einer Gedächtnisfunktion. Es ist kaum möglich, die dabei erhaltene Gedächtnisfunktion als Funktion der Invarianten der der Tensoren darzustellen. Die zweite Normal-SpannungsdifferenzN ₂ des Modells ist nicht Null und hat einen negativen Wert. Dies ist nach unserem Modell eine Folge der Deformationsabhängigkeit des Entschlaufungsprozesses. Die Theorie wird mit dem experimentellen Daten für eine LDPE-Schmelze verglichen, wobei sich zeigt, daß das Modell die wesentlichen Merkmale des Scherverhaltens der LDPE-Schmelze gut erklärt.

     

Entrapment and release of sodium polystyrene sulfonate (SPS) from calcium alginate gel beads

The release of sodium polystyrene sulfonate (SPS) from calcium alginate hydrogel beads has been studied. It has been shown that the structure of the cross-linked calcium alginate network is of primary importance in the retention and/or release of the SPS. This has been evidenced by studying the influence of Ca²⁺ concentration, molar masses (M_n) and the ratio of mannuronic acid/guluronic acid components. A minimum in the SPS release is observed in relation with the organization of the network structure. Conditions inducing the organization of a strong gel (e.g. high Ca²⁺ concentration for example) are not always related to a low release. A good control of release is found when a compromise between a well-structured hydrogel and sterical consideration of SPS is reached.     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.