Sequence of operations analysis for dynamic data structures

This paper introduces a rather general technique for computing the average-case performance of dynamic data structures, subjected to arbitrary sequences of insert, delete, and search operations. The method allows us effectively to evaluate the integrated cost of various interesting data structure implementations, for stacks, dictionaries, symbol tables, priority queues, and linear lists; it can thus be used as a basis for measuring the efficiency of each proposed implementation. For each data type, a specific continued fraction and a family of orthogonal polynomials are associated with sequences of operations: Tchebycheff for stacks, Laguerre for dictionaries, Charlier for symbol tables, Hermite for priority queues, and Meixner for linear lists. Our main result is an explicit expression, for each of the above data types, of the generating function for integrated costs, as a linear integral transform of the generating functions for individual operation costs. We use the result to compute explicitly integrated costs of various implementations of dictionaries and priority queues.     

A simulation approach to cost-effectiveness and cost-benefit calculations of screening for the early detection of disease

The computer simulation program Miscan, developed for analysis, prediction and optimization of screening for early detection of disease, has been extended to enable full cost-effectiveness and cost-benefit calculations. The user specifies which of the available cost- and effectiveness-items are to be used and can choose the valuation per unit for each item. The program computes the volume of each item for scenarios with and without screening, and calculates the costs and effectiveness of the simulated screening policy. The program allows for discounting and present value computations, for scale effects, and for quality adjustment of life years for age and disease stage. The use of the program is illustrated with a model of cervical cancer screening that was based on data from the pilot project in the Netherlands. Two screening policies are compared for several discount rates, and for several exchange rates between costs and health effects.     

Determinants of matrices over semirings

In this paper, the concept of determinants for the matrices over a commutative semiring is introduced, and a development of determinantal identities is presented. This includes a generalization of the Laplace and Binet–Cauchy Theorems, as well as on adjoint matrices. Also, the determinants and the adjoint matrices over a commutative difference-ordered semiring are discussed and some inequalities for the determinants and for the adjoint matrices are obtained. The main results in this paper generalize the corresponding results for matrices over commutative rings, for fuzzy matrices, for lattice matrices and for incline matrices.     

Pricing strategies for perishable products: the case of Vienna and the hotel reservation system hrs.com

Consider a retailer who sells perishable products for which there is uncertain demand. Yield management with dynamic pricing is a standard practice that firms use for revenue management. For perishable products, recent analysis has focused on the distribution of flight capacity, referred to as ticket sales. Other non- storable, non-transportable, immaterial hospitality products include hotel capacity. The article discusses the extent to which hotel pricing strategies vary within the internet distribution system hrs.com. This study focuses on the distribution of hotel rooms available for booking on the internet for Vienna and gives an outlook to Euroland capitals. The main research interests are the underlying pricing models and the setting of the end price. Data was taken from hrs.com, which is the most important specialist for hotel room internet distribution in Germany according to recent studies by KMPG and others. The results include the identification of different pricing strategy clusters with regard to hotel category and hotel availability over a 22-day period for Vienna and one city from all Euroland countries (the capitals were studied for all cases except for the Netherlands, for which data was collected for Amsterdam). The study took the arrival days Mondays, Tuesdays, Wednesdays and Thursdays into account, and used data for all these days from the 11th of July, 2005, to the 10th of October, 2005, for Vienna, and the first and the last of these dates as a comparison base for the other Euroland cities.     

Half Space and Quarter Space Dirichlet Problems for the Partial Differential Equation

A customary, heuristic, method, by which the Poisson integral formula for the Dirichlet problem, for the half space, for Laplace's equation is obtained, involves Green's function, and Kelvin's method of images. Although this heuristic method leads one to guess the correct result, this Poisson formula still has to be verified directly, independently of the method by which it was arrived at, in order to be absolutely certain that a solution of the Dirichlet problem for the half space, for Laplace's equation, has been actually obtained. A similar heuristic method, as seems to be generally known, could be followed in solving the Dirichlet problem, for the half space, for the equation where is a real constant. However, in Part 1, a different, labor-saving, method is used to study Dirichlet problems for the equation. This method is essentially based on what Hadamard called the method of descent. Indeed, it is shown that he who has solved the half space Dirichlet problem for Laplace's equation has already solved the half space Dirichlet problem for the equation In Part 2, the solution formula for the quarter space Dirichlet problem for Laplace's equation is obtained from the Poisson integral formula for the half space Dirichlet problem for Laplace's equation. A representation theorem for harmonic functions in the quarter space is deduced. The method of descent is used, in Part 3, to obtain the solution formula for the quarter space Dirichlet problem for the equation by means of the solution formula for the quarter space Dirichlet problem for Laplace's equation. So that, indeed, it is also shown that he who has solved the quarter space Dirichlet problem for Laplace's equation has already solved the quarter space Dirichlet problem for the " equation" For the sake of completeness and clarity, and for the convenience of the reader, the appendix, at the end of Part 3, contains a detailed proof that the Poisson integral formula solves the half space Dirichlet problem for Laplace's equation. The Bibliography for Parts 1,2, 3 is to be found at the end of Part 1.     

On bounds for the mode and median of the generalized hyperbolic and related distributions

Except for certain parameter values, a closed form formula for the mode of the generalized hyperbolic (GH) distribution is not available. In this paper, we exploit results from the literature on modified Bessel functions and their ratios to obtain simple but tight two-sided inequalities for the mode of the GH distribution for general parameter values. As a special case, we deduce tight two-sided inequalities for the mode of the variance-gamma (VG) distribution, and through a similar approach we also obtain tight two-sided inequalities for the mode of the McKay Type I distribution. The analogous problem for the median is more challenging, but we conjecture some monotonicity results for the median of the VG and McKay Type I distributions, from we which we conjecture some tight two-sided inequalities for their medians. Numerical experiments support these conjectures and also lead us to a conjectured tight lower bound for the median of the GH distribution.     

流动稳定性弱非线性理论的重新考虑*

弱非性理论已被广泛用于流动稳定性理论及其它领域.然而其应用对某些问题虽是成功的,但对另一些问题,其结果却常不令人满意,特别是对转捩或自由剪切流中涡的演化这类问题,这时理论研究的目的不是寻找稳态解,而是预测演化过程.在本文中,我们将研究不成功的原因并建议一些改进的办法.     

非强制混合向量变分不等式解的存在性研究

本文利用例外簇方法研究非强制混合向量变分不等式的弱有效解的存在性:首先证明若混合向量变分不等式问题不存在例外簇,则混合向量变分不等式问题的弱有效解集为非空集合:利用向量值映射的渐近映射给出自反Banach空间中非强制混合向量变分不等式的弱有效解集不存在例外簇的充分条件,从而得到混合向量变分不等式问题的弱有效解的存在性结...     

Superconvergence of mixed finite element methods for parabolic problems with nonsmooth initial data

Summary. A semidiscrete mixed finite element approximation to parabolic initial-boundary value problems is introduced and analyzed. Superconvergence estimates for both pressure and velocity are obtained. The estimates for the errors in pressure and velocity depend on the smoothness of the initial data including the limiting cases of data in and data in , for sufficiently large. Because of the smoothing properties of the parabolic operator, these estimates for large time levels essentially coincide with the estimates obtained earlier for smooth solutions. However, for small time intervals we obtain the correct convergence orders for nonsmooth data. Received July 30, 1995 / Revised version received October 14, 1996     

基于多维线性扩展的模糊联盟合作对策tau值性质与计算方法

研究模糊联盟合作对策tau值的计算方法及其性质. 利用多维线性扩展方法定义了模糊联盟合作对策的tau值, 证明了其存在性、唯一性等性质, 并推导出基于多维线性扩展凸模糊联盟合作对策tau值的计算公式. 研究结果发现, 基于多维线性扩展的模糊联盟合作对策tau值是对清晰联盟合作对策tau值的扩展, 而清晰联盟合作对策tau值仅是其特例. 特别地, 对于凸模糊联盟合作对策, 利用其tau值计算公式, 可进一步简化求解过程.     

Matrix correction of a dual pair of improper linear programming problems

A matrix is sought that solves a given dual pair of systems of linear algebraic equations. Necessary and sufficient conditions for the existence of solutions to this problem are obtained, and the form of the solutions is found. The form of the solution with the minimal Euclidean norm is indicated. Conditions for this solution to be a rank one matrix are examined. On the basis of these results, an analysis is performed for the following two problems: modifying the coefficient matrix for a dual pair of linear programs (which can be improper) to ensure the existence of given solutions for these programs, and modifying the coefficient matrix for a dual pair of improper linear programs to minimize its Euclidean norm. Necessary and sufficient conditions for the solvability of the first problem are given, and the form of its solutions is described. For the second problem, a method for the reduction to a nonlinear constrained minimization problem is indicated, necessary conditions for the existence of solutions are found, and the form of solutions is described. Numerical results are presented.     

The transfer of systems technology: logistics systems for underdeveloped countries

New approaches to large scale industrial development in less developed countries require closer attention to the design of the support systems needed to keep the plants running after construction. System redundancy, loose coupling of subsystems and the capability for adaptive learning become particularly important design principles given the complexity of the operating environment. This paper discusses the application of these principles to logistics systems design for a multibillion dollar steel plant. Specific guidelines are developed for the requisitioning process for spare parts and materials, for item identification, for the use of assemblies and for the organization of storage and retrieval procedures.     

BATE curve in assessment of clinical utility of predictive biomarkers

In this paper,for time-to-event data,we propose a new statistical framework for casual inference in evaluating clinical utility of predictive biomarkers and in selecting an optimal treatment for a particular patient.This new casual framework is based on a new concept,called Biomarker Adjusted Treatment Effect (BATE) curve.The BATE curve can be used for assessing clinical utility of a predictive biomarker,for designing a subsequent confirmation trial,and for guiding clinical practice.We then propose semi-parametric methods for estimating the BATE curves of biomarkers and establish asymptotic results of the proposed estimators for the BATE curves.We also conduct extensive simulation studies to evaluate finite-sample properties of the proposed estimation methods.Finally,we illustrate the application of the proposed method in a real-world data set.     

Explicit Coercivity Estimates for the Linearized Boltzmann and Landau Operators

We prove explicit coercivity estimates for the linearized Boltzmann and Landau operators, for a general class of interactions including any inverse-power law interactions, and hard spheres. The functional spaces of these coercivity estimates depend on the collision kernel of these operators. They cover the spectral gap estimates for the linearized Boltzmann operator with Maxwell molecules, improve these estimates for hard potentials, and are the first explicit coercivity estimates for soft potentials (including in particular the case of Coulombian interactions). We also prove a regularity property for the linearized Boltzmann operator with non locally integrable collision kernels, and we deduce from it a new proof of the compactness of its resolvent for hard potentials without angular cutoff.     

四阶抛物偏微分方程的H1-Galerkin混合元方法及数值模拟

到目前为止, H¹-Galerkin 混合有限元方法研究的问题仅局限于二阶发展方程. 然而对于高阶发展方程, 特别是重要的四阶发展方程问题的研究却没有出现. 本文首次提出四阶发展方程的H¹-Galerkin 混合有限元方法, 为了给出理论分析的需要, 我们考虑四阶抛物型发展方程. 通过引进三个适当的中间辅助变量, 形成四个一阶方程组成的方程组系统, 提出四阶抛物型方程的H¹-Galerkin 混合有限元方法. 得到了一维情形下的半离散和全离散格式的最优收敛阶误差估计和多维情形的半离散格式误差估计, 并采用迭代方法证明了全离散格式的稳定性. 最后, 通过数值例子验证了提出算法的可行性. 在一维情况下我们能够同时得到未知纯量函数、一阶导数、负二阶导数和负三阶导数的最优逼近解, 这一点是以往混合元方法所不能得到的.     

The Axiom of Choice in Second-Order Predicate Logic

The present article deals with the power of the axiom of choice (AC) within the second-order predicate logic. We investigate the relationship between several variants of AC and some other statements, known as equivalent to AC within the set theory of Zermelo and Fraenkel with atoms, in Henkin models of the one-sorted second-order predicate logic with identity without operation variables. The construction of models follows the ideas of Fraenkel and Mostowski. It is e. g. shown that the well-ordering theorem for unary predicates is independent from AC for binary predicates and from the trichotomy law for unary predicates. Moreover, we show that the AC for binary predicates follows neither from the trichotomy law for unary predicates nor from Zorn's lemma for unary predicates nor from the formalization of the axiom of choice for disjoint families of sets for binary predicates, and that the trichotomy law for unary predicates does not follow from AC for binary predicates. Mathematics Subject Classification: 03B15, 03E25, 04A25.     

Fast Algorithms for Identification and Comparison of Braids

A method for constructing algorithms solving the word and comparison problems for mapping class groups (in particular, for the braid group) is presented, and a family of one-side invariant orderings on the mapping class group of a surface with boundary is described. A method for constructing comparison algorithms for all finite orderings on the mapping class group of any surface with boundary is described, a fast and simple comparison algorithm for the Dehornoy order on the braid group is presented, examples of normal forms for braid groups are given, and algorithms for finding the forms are indicated. Bibliography: 15 titles.     

Bounds for Shannon and Zipf‐Mandelbrot entropies

Shannon and Zipf‐Mandelbrot entropies have many applications in many applied sciences, for example, in information theory, biology and economics, etc. In this paper, we consider two refinements of the well‐know Jensen inequality and obtain different bounds for Shannon and Zipf‐Mandelbrot entropies. First of all, we use some convex functions and manipulate the weights and domain of the functions and deduce results for Shannon entropy. We also discuss their particular cases. By using Zipf‐Mandelbrot laws for different parameters in Shannon entropies results, we obtain bounds for Zipf‐Mandelbrot entropy. The idea used in this paper for obtaining the results may stimulate further research in this area, particularly for Zipf‐Mandelbrot entropy.     

Scheduling problems in transportation networks of line topology

In this paper we consider online scheduling problems for linear topology under various objective functions: minimizing the maximum completion time, minimizing the largest delay, and minimizing the sum of completion times. We give optimal solutions for uni-directional version of the problem for each of the objectives and show that for the two-directional versions of each problem, no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions. We also propose 2-approximation on-line algorithms for the MinMakespan and the MinSum minimization objectives. We also prove that no online algorithm can deterministically achieve the optimal solution for any of the considered objective functions for the weighted case of uni-directional scenarios.