Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

ARTIFICIAL NEURAL NETWORK MODELING FOR REFORESTATION DESIGN THROUGH THE DOMINANT TREES BOLE‐VOLUME ESTIMATION

Abstract In the management of restoration reforestations or recreational reforestations of trees, the density of the planted trees and the site conditions can influence the growth and bole volume of the dominant tree. The ability to influence growth of these trees in a reforestation contributes greatly to the formation of large dimension trees and thereby to the production of commercially valuable wood. The potential of two artificial neural network (ANN) architectures in modeling the dominant Pinus brutia tree bole volume in reforestation configuration at 12 years of age was investigated: (1) the multilayer perceptron architecture using a back‐propagation algorithm and (2) the cascade‐correlation architecture, utilizing (a) either the nonlinear Kalman's filter theory or (b) the adaptive gradient descent learning rule. The incentive for developing bole‐volume equations using ANN techniques was to demonstrate an alternative new methodology in the field of reforestation design, which would enable estimation and optimization of the bole volume of dominant trees in reforestations using easily measurable site and competition factors. The usage of the ANNs for the estimation of dominant tree bole volume through site and competition factors can be a very useful tool in forest management practice.     

The tree and forest spaces with applications to initial-value problem methods

Tree and forest spaces, which are at the heart of the theory of Runge–Kutta methods, are formulated recursively, and it is shown that the forest space is an algebra. To obtain order conditions in a systematic manner, Banach algebras are introduced to generate both the elementary weights for a general Runge–Kutta method and the corresponding quantities based on the Picard integral. To connect these two concepts, the Picard integral is written as the limiting case of an s-stage Runge–Kutta method, equivalent to s steps of the Euler method, as s tends to infinity. This approach makes it possible to make direct use of the tree space without going over to the dual space. By choosing linear combinations of trees, appropriate to a particular application, it is shown how to obtain alternative ways of writing the order conditions. This leads to a simpler and more direct derivation of particular methods.     

STRUCTURED MODELS OF PATTERN FORMATION OF TREE POPULATIONS

ABSTRACT. The problem of mathematical modeling of the phenomenon of appearance and forming of allocated tree subpopulations, called gap, locus, cenon is studied. Such a subpopulation (not a single tree) is considered as an individual object of the forest community. A mathematical model describing the phenomenon of cenon formation as a result of natural dynamics of initial heterogeneous tree subpopulation is suggested. The model is constructed in the framework of a structural population model of one generation with distributed values of parameters and initial states. The “biological basis” of cenon formation is the so-called discriminating death. It is shown that this component of death accounted for the model results in the formation of the comparatively homogeneous subpopulation from the initial heterogeneous sub-population of trees.     

Stochastic lot-sizing with backlogging: computational complexity analysis

For a multi-stage stochastic programming problem, one approach is to explore a scenario tree based formulation for the problem and solve the formulation efficiently. There has been significant research progress on how to generate scenario trees in the literature. However, there is limited work on analyzing the computational complexity of the scenario-tree based formulation that considers the number of tree nodes as the input size. In this paper, we use stochastic lot-sizing problems as examples to study the computational complexity issues for the scenario-tree based formulations. We develop production path properties and a general dynamic programming framework based on these properties. The dynamic programming framework allows us to show that the optimal value function is piecewise linear and continuous, which enables us to develop polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain conditions. As special cases, we develop polynomial time algorithms that run in O(n²){\mathcal{O}(n^2)} and O(n²T log n){\mathcal{O}(n^2T\,{\rm log}\,n)} times, respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of the scenario tree structure.     

On Minimum Edge Ranking Spanning Trees

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.     

A new smoothing and regularization Newton method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a nonsmooth system of equations. In this paper, we propose a new smoothing and regularization Newton method for solving nonlinear complementarity problem with P ₀-function (P ₀-NCP). Without requiring strict complementarity assumption at the P ₀-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter ε in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods.     

A New Approach to the Algebraic Structures for Integration Methods

The analysis of compositions of Runge-Kutta methods involves manipulations of functions defined on rooted trees. Existing formulations due to Butcher [1972], Hairer and Wanner [1974], and Murua and Sanz-Serna [1999], while equivalent, differ in details. The subject of the present paper is a new recursive formulation of the composition rules. This both simplifies and extends the existing approaches. Instead of using the order conditions based on trees, we propose the construction of the order conditions using a suitably chosen basis on the tree space. In particular, the linear structure of the tree space gives a representation of the C and D simplifying assumptions on trees which is not restricted to Runge-Kutta methods. A proof of the group structure of the set of elementary weight functions satisfying the D simplifying assumptions is also given is this paper.     

A multilevel algorithm for the biharmonic problem

Summary A finite element discretization of the mixed variable formulation of the biharmonic problem is considered. A multilevel algorithm for the numerical solution of the discrete equations is described. Convergence is proved under the assumption ofH ³-regularity.     

A few logs suffice to build (almost) all trees (I)

A phylogenetic tree, also called an “evolutionary tree,” is a leaf‐labeled tree which represents the evolutionary history for a set of species, and the construction of such trees is a fundamental problem in biology. Here we address the issue of how many sequence sites are required in order to recover the tree with high probability when the sites evolve under standard Markov‐style i.i.d. mutation models. We provide analytic upper and lower bounds for the required sequence length, by developing a new polynomial time algorithm. In particular, we show when the mutation probabilities are bounded the required sequence length can grow surprisingly slowly (a power of log n) in the number n of sequences, for almost all trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 153–184, 1999     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

State vector solutions for nonaxisymmetric problem of multilayered half space piezoelectric medium

A state space formulation is established for the nonaxisymmetric space problem of transversely isotropic piezoelectric media in a system of cylindrical coordinate by introducing the state vector. Using the Hankel transform and the Fourier series, the state vector equations are transformed into ordinary differential equations. By the use of the matrix methods, the analytical solutions of a single piezoelectric layer are presented in the form of the product of initial state variables and transfer matrix. The applications of state vector solutions are discussed. An analytical solution for a semiinfinite piezoelectric medium subjected to the vertical point forceP _z, horizontal point forceP _x along x-direction and point electric charge Q at the origin of the surface is presented. According to the continuity conditions at the interfaces, the general solution formulation forN-layered transversely isotropic piezoelectric media is given. Project supported by the National Natural Science Foundation of China (Grant No. 59648001).     

An Algorithm for Generating Individualized Treatment Decision Trees and Random Forests

With new treatments and novel technology available, precision medicine has become a key topic in the new era of healthcare. Traditional statistical methods for precision medicine focus on subgroup discovery through identifying interactions between a few markers and treatment regimes. However, given the large scale and high dimensionality of modern datasets, it is difficult to detect the interactions between treatment and high-dimensional covariates. Recently, novel approaches have emerged that seek to directly estimate individualized treatment rules (ITR) via maximizing the expected clinical reward by using, for example, support vector machines (SVM) or decision trees. The latter enjoys great popularity in clinical practice due to its interpretability. In this article, we propose a new reward function and a novel decision tree algorithm to directly maximize rewards. We further improve a single tree decision rule by an ensemble decision tree algorithm, ITR random forests. Our final decision rule is an average over single decision trees and it is a soft probability rather than a hard choice. Depending on how strong the treatment recommendation is, physicians can make decisions based on our model along with their own judgment and experience. Performance of ITR forest and tree methods is assessed through simulations along with applications to a randomized controlled trial (RCT) of 1385 patients with diabetes and an EMR cohort of 5177 patients with diabetes. ITR forest and tree methods are implemented using statistical software R (https://github.com/kdoub5ha/ITR.Forest). Supplementary materials for this article are available online.     

Derived Sets for Weak Multiobjective Optimization Problems with State and Control Variables

The concept of a K-gradient, introduced in Ref. 1 in order to generalize the concept of a derived convex cone defined by Hestenes, is extended to weak multiobjective optimization problems including not only a state variable, but also a control variable. The new concept is employed to state multiplier rules for the local solutions of such dynamic multiobjective optimization problems. An application of these multiplier rules to the local solutions of an abstract multiobjective optimal control problem yields general necessary optimality conditions that can be used to derive concrete maximum principles for multiobjective optimal control problems, e.g., problems described by integral equations with additional functional constraints.     

Using scenario trees and progressive hedging for stochastic inventory routing problems

The Stochastic Inventory Routing Problem is a challenging problem, combining inventory management and vehicle routing, as well as including stochastic customer demands. The problem can be described by a discounted, infinite horizon Markov Decision Problem, but it has been showed that this can be effectively approximated by solving a finite scenario tree based problem at each epoch. In this paper the use of the Progressive Hedging Algorithm for solving these scenario tree based problems is examined. The Progressive Hedging Algorithm can be suitable for large-scale problems, by giving an effective decomposition, but is not trivially implemented for non-convex problems. Attempting to improve the solution process, the standard algorithm is extended with locking mechanisms, dynamic multiple penalty parameters, and heuristic intermediate solutions. Extensive computational results are reported, giving further insights into the use of scenario trees as approximations of Markov Decision Problem formulations of the Stochastic Inventory Routing Problem.     

Analysis of three graph parameters for random trees

We consider three basic graph parameters, the node‐independence number, the path node‐covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size n asymptotically ～μn and ～νn, where the constants μ and ν depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009