Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Computing monotone disjoint paths on polytopes

The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph consisting of the set of vertices and arcs of a polytope P directed by a linear objective function in general position. The study of paths on polytopal digraphs stems from a long standing problem, that of designing a polynomial-time pivot method, or proving none exists. To study disjoint paths it would be useful to have a tool to compute them. Without explicitly computing the digraph we develop an algorithm to compute a maximum cardinality set of source to sink paths in a polytope, even in the presence of degeneracy. The algorithm uses a combination of networks flows, the simplex method, and reverse search. An implementation is available.     

危险品集成物流管理系统选址-选线模型研究

以路网的危险度瓶颈限制为切入点研究了一类危险品集成物流管理系统选址—选线问题,对应于路网危险度瓶颈限制引入安全费用非递减函数,并根据运输工具的安全配置等级构造该等级下的子网络,物流系统的选址—选线结果随着路网的调整而不断变化.危险品集成物流系统的管理存在多个目标,文中首先分析了成本、风险和风险公平性等优化目标,在说明了建模的假设条件后,建立了基于路网危险度瓶颈限制的危险品集成物流系统选址—选线的多目标模型,并根据模型给出了一种启发式算法,最后用一个算例对模型进行了数值演算.     

双层规划在城市交通污染控制中的一个应用

本文从控制城市交通污染的角度出发,考虑到用户的路径选择行为,采用双层规划模型描述城市交通管理与污染控制问题,并给出了相应的启发式求解算法及算例,在此基础上,提出了城市交通管理与污染控制框架。     

Eliminating a sparse data problem in nonparametric bivariate survival analysis with an application to women's age at first marriage and age at first birth

A new solution is proposed for a sparse data problem arising in nonparametric estimation of a bivariate survival function. Prior information, if available, can be used to obtain initial values for the EM algorithm. Initial values will completely determine estimates of portions of the distribution which are not identifiable from the data, while having a minimal effect on estimates of portions of the distribution for which the data provide sufficient information. Methods are applied to the distribution of women's age at first marriage and age at birth of first child, using data from the Current Population Surveys of 1975 and 1986.     

Modelling mass-size particle data by finite mixtures

A minimum distance procedure, analogous to maximum likelihood for multinomial data, is employed to fit mixture models to mass-size relative frequencies recorded for some clay soils of southeastern Australia. Log hyperbolic component distributions are considered initially and it is shown how they can be fitted satisfactorily at least to ungrouped data using a generalized EM algorithm. A computationally more convenient model with log skew Laplace components is subsequently shown to suffice. It is demonstrated how it can be fitted to the data in their original grouped form. Consideration is given also to the provision of standard errors using the idea of a quasi-sample size.     

Testing for the maximum mean in a mixture of normals

We consider the test of the null hypothesis that the largest mean in a mixture of an unknown number of normal components is less than or equal to a given threshold. This test is motivated by the problem of assessing whether the Soviet Union has been operating in compliance with the Nuclear Test Ban Treaty. In our analysis, the number of normal components is determined using Akaike's Information Criterion while the hypothesis test itself is based on asymptotic results given by Behboodian for a mixture of two normal components. A bootstrap approach is also considered for estimating the standard error of the largest estimated mean. The performance of the testa are examined through the use of simulation.     

Testing for or against a trend in odds ratios

Consider data arranged into k × 2 × 2 contingency tables. The principal result of this paper is the derivation of the likelihood ratio test and its asymptotic distribution for testing for or against an order restriction placed upon the odds ratios. We will show that the limiting distributions are of chi-bar square type and give the expression of the weighting values.     

Likelihood estimation of missing cell means in the fixed model analysis of variance

This paper examines the formation of maximum likelihood estimates of cell means in analysis of variance problems for cells with missing observations. Methods of estimating the means for missing cells has a long history which includes iterative maximum likelihood techniques, approximation techniques and ad hoc techniques. The use of the EM algorithm to form maximum likelihood estimates has resolved most of the issues associated with this problem. Implementation of the EM algorithm entails specification of a reduced model. As demonstrated in this paper, when there are several missing cells, it is possible to specify a reduced model that results in an unidentifiable likelihood. The EM algorithm in this case does not converge, although the slow divergence may often be mistaken by the unwary as convergence. This paper presents a simple matrix method of determining whether or not the reduced model results in an identifiable likelihood, and consequently in an EM algorithm that converges. We also show the EM algorithm in this case to be equivalent to a method which yields a closed form solution.