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.     

Extension of multivariate regression trees to interval data. Application to electricity load profiling

Summary  Several data can be presented as interval curves where intervals reflect a within variability. In particular, this representation is well adapted for load profiles, which depict the electricity consumption of a class of customers. Electricity load profiling consists in assigning a daily load curve to a customer based on their characteristics such as energy requirement. Within the load profiling scope, this paper investigates the extension of multivariate regression trees to the case of interval dependent (or response) variables. The tree method aims at setting up simultaneously load profiles and their assignment rules based on independent variables. The extension of multivariate regression trees to interval responses is detailed and a global approach is defined. It consists in a first stage of a dimension reduction of the interval response variables. Thereafter, the extension of the tree method is applied to the first principal interval components. Outputs are the classes of the interval curves where each class is characterized both by an interval load profile (e.g. the class prototype) and an assignment rule based on the independent variables.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/∞ system revisited: finiteness,summability, long range dependence,and reverse engineering

We explore M/G/∞ systems ‘fed’ by Poissonian inflows with infinite arrival rates. Three processes – corresponding to the system's state, workload, and queue-size – are studied and analyzed. Closed form formulae characterizing the system's stationary structure and correlation structure are derived. And, the issues of queue finiteness, workload summability, and Long Range Dependence are investigated. We then turn to devise a ‘reverse engineering’ scheme for the design of the system's correlation structure. Namely: how to construct an M/G/∞ system with a pre-desired ‘target’ workload/queue auto-covariance function. The ‘reverse engineering’ scheme is applied to various examples, including ones with infinite queues and non-summable workloads. AMS Subject Classifications Primary: 60K25; Secondary: 60G55, 60G10     

随机删失场合半参数回归模型参数估计的重对数律‘

本文探讨了随机删失场合半参数回归模型的参数估计问题.考虑半参数回归模型Y =X}}3 + g(T)十。，其中(X,T)’为取值于Kp X [0,1〕上的随机向量，月为1'维未知参数向量，8为定义于【0.1]上的未知函数，。为随机误差，Ee = 0 . Eez = az }。未知，且(X ,T)与。独立，).被一个与之独立的随机变量V所截.此时仅能观察到:Z=min(Y,V),o=1(Y簇V)，参数I3,az的估计量禽及公 z可综合非参数的权函数估计法与参数的最小二乘估计方法得到.本文对核函数的情形得到了念及ar z的精确收敛速度即重对数律.     

左截断右删失下核密度估计的L1距离的界

本文在左截断右删失数据下获得了概论密度的核估计的L1距离的一个上界．     

浅议物理实验教学环节改革

为进一步提高大学物理实验的教学质量，本文就实验课的预习、操作、实验报告的撰写及考核方法进行了探讨。     

Recent developments in the statistical processing of textual data

Statisticians are accustomed to processing numerical, ordinal or nominal data. In many circumstances, such as socio-economic, epidemiologic sample surveys and documentary data bases, this data is juxtaposed with textual data (for example, responses to open questions in surveys). This article presents a series of language-independent procedures based upon applying multivariate techniques (such as correspondence analysis and clustering) to sets of generalized lexical profiles. The generalized lexical profile of a text is a vector whose components are the frequencies of each word (graphical form) or ‘repeated segment’ (sequence of words appearing with a significant frequency in the text). The processing of such large (and often sparse) vectors and matrices requires special algorithms. The main outputs are the following: (1) printouts of the characteristic words and characteristic responses for each category of respondent (these categories are generally derived from available nominal variables); (2) graphical displays of the proximities between words or segments and categories of respondents; (3) when analysing a combination of several texts: graphical displays of proximities between words or segments and each text, or between words or segments and groupings of texts. The systematic use of ‘repeated segments’ provides a valuable help in interpreting the results from a semantic point of view.     

The k-means range algorithm for personalized data clustering in e-commerce

This paper describes the k-means range algorithm, a combination of the partitional k-means clustering algorithm with a well known spatial data structure, namely the range tree, which allows fast range searches. It offers a real-time solution for the development of distributed interactive decision aids in e-commerce since it allows the consumer to model his preferences along multiple dimensions, search for product information, and then produce the data clusters of the products retrieved to enhance his purchase decisions. This paper also discusses the implications and advantages of this approach in the development of on-line shopping environments and consumer decision aids in traditional and mobile e-commerce applications.     

光盘阵列系统的一种性能优化方法

提出了一种用低性能驱动器组建高性能光盘阵列系统性能的优化方法。针对传统的低性能光盘驱动器(驱动器内部数据传输率及接口速率均较低),提出了一种新型的数据传输模式。采用此优化方法可以使光盘阵列系统的整体性能得到较大地提高。同时还可以提高系统整体的性价比。