Complexity of Reducing the Delay between Two Nodes by Node-based and Edge-based Upgrading Strategies

For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t not greater than U. In this paper, we present some NP-hard results for the delay improvement problems.     

Asymptotics for Kernel Estimation of Slicing Average Third-Moment Estimation

To estimate central dimension-reduction space in multivariate nonparametric rcgression, Sliced Inverse Regression （SIR）, Sliced Average Variance Estimation （SAVE） and Slicing Average Third-moment Estimation （SAT） have been developed, Since slicing estimation has very different asymptotic behavior for SIR, and SAVE, the relevant study has been madc case by case, when the kernel estimators of SIH and SAVE share similar asymptotic properties. In this paper, we also investigate kernel estimation of SAT. We. prove the asymptotic normality, and show that, compared with tile existing results, the kernel Slnoothing for SIR, SAVE and SAT has very similar asymptotic behavior,     

Triangular Cm interpolation by rational functions

Two general local C^m triangular interpolation schemes by rational functions from C^m data are proposed for any nonnegative integer m. The schemes can have either 2m+1 order algebraic precision if the required data are given on vertices and edges, or m+E[m/2]+1 or m+1 order algebraic precision if the data are given only at vertices. The orders of the interpolation error are estimated. Examples that show the correctness and effectiveness of the scheme are presented. Supported partially by NSFC under Project 1967108 and Croucher Foundation of Hong Kong; Supported also by FRG of Hong Kong Paptist University.     

Maximum variance of order statistics

Yang (1982,Bull. Inst. Math. Acad. Sinica,10(2), 197–204) proved that the variance of the sample median cannot exceed the population variance. In this paper, the upper bound for the variance of order statistics is derived, and it is shown that this is attained by Bernoulli variates only. The proof is based on Hoeffding's identity for the covariance.     

Bayes estimation of number of signals

Bayes estimation of the number of signals, q, based on a binomial prior distribution is studied. It is found that the Bayes estimate depends on the eigenvalues of the sample covariance matrix S for white-noise case and the eigenvalues of the matrix S ₂ (S ₁+A)^–1 for the colored-noise case, where S ₁ is the sample covariance matrix of observations consisting only noise, S ₂ the sample covariance matrix of observations consisting both noise and signals and A is some positive definite matrix. Posterior distributions for both the cases are derived by expanding zonal polynomial in terms of monomial symmetric functions and using some of the important formulae of James (1964, Ann. Math. Statist., 35, 475–501).     

Some Properties of A Lack-of-Fit Test for a Linear Errors in Variables Model

The relationship between the linear errors-in-variables model and the corresponding ordinary linear model in statistical inference is studied. It is shown that normality of the distribution of covariate is a necessary and sufficient condition for the equivalence. Therefore, testing for lack-of-fit in linear errors-in-variables model can be converted into testing for it in the corresponding ordinary linear model under normality assumption. A test of score type is constructed and the limiting chi-squared distribution is derived under the null hypothesis.Furthermore, we discuss the power of the test and the choice of the weight function involved in the test statistic.     

The superconvergence of Newton–Cotes rules for the Hadamard finite-part integral on an interval

We study the general (composite) Newton–Cotes rules for the computation of Hadamard finite-part integral with the second-order singularity and focus on their pointwise superconvergence phenomenon, i.e., when the singular point coincides with some a priori known point, the convergence rate is higher than what is globally possible. We show that the superconvergence rate of the (composite) Newton–Cotes rules occurs at the zeros of a special function and prove the existence of the superconvergence points. Several numerical examples are provided to validate the theoretical analysis. The work of J. Wu was partially supported by the National Natural Science Foundation of China (No. 10671025) and a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. CityU 102507). The work of W. Sun was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. City U 102507) and the National Natural Science Foundation of China (No. 10671077).     

Empirical likelihood for partial linear models

In this paper the empirical likelihood method due to Owen (1988,Biometrika,75, 237–249) is applied to partial linear random models. A nonparametric version of Wilks' theorem is derived. The theorem is then used to construct confidence regions of the parameter vector in the partial linear models, which has correct asymptotic coverage. A simulation study is conducted to compare the empirical likelihood and normal approximation based method. Research supported by NNSF of China and a grant to the first author for his excellent Ph.D. dissertation work in China. Research supported by Hong Kong RGC CERG No. HKUST6162/97P.     

Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].     

The complexity of recognizing linear systems with certain integrality properties

Let A be a 0 − 1 matrix with precisely two 1’s in each column and let 1 be the all-one vector. We show that the problems of deciding whether the linear system (1) defines an integral polyhedron, (2) is totally dual integral (TDI), and (3) box-totally dual integral (box-TDI) are all co-NP-complete, thereby confirming the conjecture on NP-hardness of recognizing TDI systems made by Edmonds and Giles in 1984. Supported in part by NSA grant H98230-05-1-0081 and NSF grants DMS-0556091 and ITR-0326387. Supported in part by the Research Grants Council of Hong Kong and Seed Funding for Basic Research of HKU.