Two Variations of the Minimum Steiner Problem

Given a set S of starting vertices and a set T of terminating vertices in a graph G = (V,E) with non-negative weights on edges, the minimum Steiner network problem is to find a subgraph of G with the minimum total edge weight. In such a subgraph, we require that for each vertex s S and t T, there is a path from s to a terminating vertex as well as a path from a starting vertex to t. This problem can easily be proven NP-hard. For solving the minimum Steiner network problem, we first present an algorithm that runs in time and space that both are polynomial in n with constant degrees, but exponential in |S|+|T|, where n is the number of vertices in G. Then we present an algorithm that uses space that is quadratic in n and runs in time that is polynomial in n with a degree O(max {max {|S|,|T|}–2,min {|S|,|T|}–1}). In spite of this degree, we prove that the number of Steiner vertices in our solution can be as large as |S|+|T|–2. Our algorithm can enumerate all possible optimal solutions. The input graph G can either be undirected or directed acyclic. We also give a linear time algorithm for the special case when min {|S|,|T|} = 1 and max {|S|,|T|} = 2.The minimum union paths problem is similar to the minimum Steiner network problem except that we are given a set H of hitting vertices in G in addition to the sets of starting and terminating vertices. We want to find a subgraph of G with the minimum total edge weight such that the conditions required by the minimum Steiner network problem are satisfied as well as the condition that every hitting vertex is on a path from a starting vertex to a terminating vertex. Furthermore, G must be directed acyclic. For solving the minimum union paths problem, we also present algorithms that have a time and space tradeoff similar to algorithms for the minimum Steiner network problem. We also give a linear time algorithm for the special case when |S| = 1, |T| = 1 and |H| = 2.An extended abstract of part of this paper appears in Hsu et al. (1996).Supported in part by the National Science Foundation under Grants CCR-9309743 and INT-9207212, and by the Office of Naval Research under Grant No. N00014-93-1-0272.Supported in part by the National Science Council, Taiwan, ROC, under Grant No. NSC-83-0408-E-001-021.     

Smoothing Time Series with Local Polynomial Regression on Time

Time series smoothers estimate the level of a time series at time t as its conditional expectation given present, past and future observations, with the smoothed value depending on the estimated time series model. Alternatively, local polynomial regressions on time can be used to estimate the level, with the implied smoothed value depending on the weight function and the bandwidth in the local linear least squares fit. In this article we compare the two smoothing approaches and describe their similarities. Through simulations, we assess the increase in the mean square error that results when approximating the estimated optimal time series smoother with the local regression estimate of the level.     

A-optimal designs for heteroscedastic multifactor regression models

Abstract

This paper searches for A-optimal designs for Kronecker product and additive regression models when the errors are heteroscedastic. Sufficient conditions are given so that A-optimal designs for the multifactor models can be built from A-optimal designs for their sub-models with a single factor. The results of an efficiency study carried out to check the adequacy of the products of optimal designs for uni-factor marginal models when these are used to estimate different multi-factor models are also reported.     

Gammaization and wishartness of dependent quadratic forms

In this paper two equivalent sets of necessary and sufficient conditions are derived for dependent quadratic forms to be distributed as multivariate gamma distribution. The procedure also gives a set of necessary and sufficient conditions for principal minors of generalized quadratic forms to be jointly distributed as the joint distribution of principal minors of a Kishart matrix.     

A test for variance-covarianch parameters in normal linear models

This paper derives a test statistic for the variance-covariance parameters which is a quadratic function of their MINQUE (Minimum Norm Quadratic Unbiased Estimation) estimates. The test is a Wald-type test, and its development closely parallels the theory used to derive a similar test for the coefficients in linear models. In fact, the derivation proceeds by first setting up the estimation problem in a derived linear model in which the dispersion parameters are the coefficients. The test statistic is shown to be the sum of the squares of independent standardized x² variables.     

Some further aspects of the löwner-ordering antitonicity of the moore-penrose inverse

A survey is given of known proofs of the antitonicity of the inverse matrix function for positive definite matrices w.r.t. the Lowner partial ordering, and of the corresponding result for the Moore-Penrose inverse of nonnegative definite matrices [the theorem of Milliken and Akdeniz (1977)]. A short new proof of the latter result is obtained by employing an extremal representation of a nonnegative definite quadratic form. Another proof of this result involving Schur complements is also given, and is seen to be extendable to the case of symmetric (not necessarily nonnegative definite) matrices. A geometrical interpretation of Milliken and Akdeniz's theorem is presented. As an application, the relationship between the concepts of greater (maximum) concentration and smaller (minimum) dispersion is considered for a pair (class) of vector-valued statistics with possibly degenerate distributions.     

Quadratic perturbation expansions of certain functions of eigenvalues and eigenvectors and their application to sensitivity analysis in multivariate methods

Tanaka (1988) lias derived the influence functions, which are equivalent to the perturbation expansions up to linear terms, of two functions of eigenvalues and eigenvectors of a real symmetric matrix, and applied them to principal component analysis. The present paper deals with the perturbation expansions up to quadratic terms of the same functions and discusses their application to sensitivity analysis in multivariate methods, in particular, principal component analysis and principal factor analysis. Numerical examples are given to show how the approximation improves with the quadratic terms.