Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 is 3-Colorable

A fully odd K₄ is a subdivision of K₄ such that each of the six edges of the K₄ is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K₄ can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture.     

On-Line Scheduling of Two-Machine Open Shops Where Jobs Arrive Over Time

We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan.Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while inthe non-clairvoyant on-line model, this processing requirement is notknown until the job is processed and completed.In both models, scheduling of a job is irrevocable.We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive).     

数值解法中的单元形状函数技巧

本文介绍从一组互不相关的函数中推导数值法中单元形状函数的简便而有效的算法,以特定的一维内插方法导出各种二维、三维的内插方法,它们对奇异性的模拟是有益的;为了适用于延伸到无限远的单元,假设形状函数类似于Lagrange多项式,但包含了一个按指数衰减的项。     

A Note on Inconsistency of NPMLE of the Distribution Function from Left Truncated and Case I Interval Censored Data

We show that under reasonable conditions the nonparametric maximum likelihood estimate (NPMLE) of the distribution function from left-truncated and case 1 interval-censored data is inconsistent, in contrast to the consistency properties of the NPMLE from only left-truncated data or only interval-censored data. However, the conditional NPMLE is shown to be consistent. Numerical examples are provided to illustrate their finite sample properties.     

Identifiable finite mixtures of location models for clustering mixed-mode data

For clustering mixed categorical and continuous data, Lawrence and Krzanowski (1996) proposed a finite mixture model in which component densities conform to the location model. In the graphical models literature the location model is known as the homogeneous Conditional Gaussian model. In this paper it is shown that their model is not identifiable without imposing additional restrictions. Specifically, for g groups and m locations, (g!)m–1 distinct sets of parameter values (not including permutations of the group mixing parameters) produce the same likelihood function. Excessive shrinkage of parameter estimates in a simulation experiment reported by Lawrence and Krzanowski (1996) is shown to be an artifact of the model's non-identifiability. Identifiable finite mixture models can be obtained by imposing restrictions on the conditional means of the continuous variables. These new identified models are assessed in simulation experiments. The conditional mean structure of the continuous variables in the restricted location mixture models is similar to that in the underlying variable mixture models proposed by Everitt (1988), but the restricted location mixture models are more computationally tractable.     

Modelling Variability in the Branching Structure of Strawberry Inflorescences

The branching structure of inflorescences of the cultivated strawberry ( Fragaria × ananassa Duch.) is very variable. This paper demonstrates that some aspects of this variability are well described by a simple stochastic model of branching that has two adjustable parameters. The model is shown to provide a good fit to data from a set of almost 700 inflorescences of the cultivar Elsanta, collected over two successive years. For one parameter the maximum likelihood estimator is a moment estimator which is fully efficient even if the detailed branching structure of the inflorescences is not recorded. This parameter provides a convenient summary of branching vigour. The maximum likelihood estimator of the second parameter must be determined iteratively and can be quite inefficient unless the full branching structure is recorded. The model demonstrates that branching structure is affected by the order in which inflorescences emerge on the plant.     

Book Reviews

Books reviewed:
David Griffiths, W. Douglas Stirling, and K. Laurence Weldon, Understanding Data: Principles and Practice of Statistics
Ingwer Borg and Patrick Groenen, Modern Multidimensional Scaling: Theory and Applications
Jeffrey H. Dorfman, Bayesian Economics Through Numerical Methods: A Guide to Econometrics and Decision-making with Prior Information
Marek Musiela and Marek Rutkowski, Martingale Methods in Financial Modelling: Theory and Applications
Aad W. van der Vaart and Jon A. Wellner, Weak Convergence and Empirical Processes     

货物运输车辆的调度算法

本文以上海煤炭公司为例,讨论了运煤车辆的计算机调度问题,提出一个数学模型及有效的近似算法。在算法实现中,采用了一些较为先进的数据结构,使运算速度及存储需求均有较大的改善。对实际算例计算结果表明,采用本算法进行运输车辆调度,经济效益比人工调度有明显的提高。     

Statistical Analysis of Marginal Count Failure Data

Manufacturers want to assess the quality andreliability of their products. Specifically, they want to knowthe exact number of failures from the sales transacted duringa particular month. Information available today is sometimesincomplete as many companies analyze their failure data simplycomparing sales for a total month from a particular departmentwith the total number of claims registered for that given month.This information—called marginal count data—is, thus,incomplete as it does not give the exact number of failures ofthe specific products that were sold in a particular month. Inthis paper we discuss nonparametric estimation of the mean numbersof failures for repairable products and the failure probabilitiesfor nonrepairable products. We present a nonhomogeneous Poissonprocess model for repairable products and a multinomial modeland its Poisson approximation for nonrepairable products. A numericalexample is given and a simulation is carried out to evaluatethe proposed methods of estimating failure probabilities undera number of possible situations.     

Modelling change in cognitive understanding with finite mixtures

Psychological theories often posit the existence of several different states. Individuals are viewed as belonging to one of the states at a given age, but with development pass to another state. A main problem in evaluating such theories is representing the transition from one state to another over age. A stochastic transition framework is proposed which should be useful in many different settings. The model is illustrated with data from a cognitive development task.