A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.     

定量型多指标决策的层次分析法探讨

本文采用等级标度与层次分析综合的方法对定量型多指标决策问题进行了讨论，它既是层次分析法在定量型多指标决策中的合理推广，同时也为定量型多指标决策问题提供了一种行之有效的方法．     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Algorithmic Aspects of Tree Amalgamation

The amalgamation of leaf-labeled trees into a single (super)tree that “displays” each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Multicriteria analysis in decision making under information uncertainty

This paper presents results of research related to multicriteria decision making under information uncertainty. The Bellman–Zadeh approach to decision making in a fuzzy environment is utilized for analyzing multicriteria optimization models (X,M models) under deterministic information. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. This circumstance permits one to generalize the classic approach to considering the uncertainty of quantitative information (based on constructing and analyzing payoff matrices reflecting effects which can be obtained for different combinations of solution alternatives and the so-called states of nature) in monocriteria decision making to multicriteria problems. Considering that the uncertainty of information can produce considerable decision uncertainty regions, the resolving capacity of this generalization does not always permit one to obtain unique solutions. Taking this into account, a proposed general scheme of multicriteria decision making under information uncertainty also includes the construction and analysis of the so-called X,R models (which contain fuzzy preference relations as criteria of optimality) as a means for the subsequent contraction of the decision uncertainty regions. The paper results are of a universal character and are illustrated by a simple example.     

On list‐coloring outerplanar graphs

We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors L (v ) for each vertex v such that (resp., ) can be L‐list‐colored (except when the graph is K₃ with identical 2‐lists). These results are best possible for each condition in the hypotheses and bounds. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 59–74, 2008     

Using a partially observable Markov chain model to assess colonoscopy screening strategies – A cohort study

Colorectal cancer (CRC) is notoriously hard to combat for its high incidence and mortality rates. However, with improved screening technology and better understanding of disease pathways, CRC is more likely to be detected at early stage and thus more likely to be cured. Among the available screening methods, colonoscopy is most commonly used in the U.S. because of its capability of visualizing the entire colon and removing the polyps it detected. The current national guideline for colonoscopy screening recommends an observation-based screening strategy. Nevertheless, there is scant research studying the cost-effectiveness of the recommended observation-based strategy and its variants. In this paper, we describe a partially observable Markov chain (POMC) model which allows us to assess the cost-effectiveness of both fixed-interval and observation-based colonoscopy screening strategies. In our model, we consider detailed adenomatous polyp states and estimate state transition probabilities based on longitudinal clinical data from a specific population cohort. We conduct a comprehensive numerical study which investigates several key factors in screening strategy design, including screening frequency, initial screening age, screening end age, and screening compliance rate. We also conduct sensitivity analyses on the cost and quality of life parameters. Our numerical result demonstrates the usability of our model in assessing colonoscopy screening strategies with consideration of partial observation of true health states. This research facilitates future design of better colonoscopy screening strategies.     

Global Priority Estimation in Multiperson Decision Making

The analytic hierarchy process generalized to synthesizing local preferences across a complex hierarchy structure into global priorities in multiperson decision making is considered in various approaches. They include classic eigenvector synthesis and multiplicative method, and several other suggested techniques, such as three-dimensional eigenvectors, and simultaneous linear and nonlinear estimations by whole hierarchy structure in synthetic optimizing procedures. A numerical example from marketing research with many criteria, subcriteria, alternatives, and respondents is presented. The quality of approximation compared by different approaches shows that the best results are produced by the nonlinear synthetic priority techniques. The techniques described have been successfully used in dozens of real-world projects and are very helpful for practical managerial decision making in complex hierarchies. Dr. Stan Lipovetsky is Senior Research Director, GfK Custom Research North America, Marketing Science, Research Center for Excellence. The author thanks Professor T. Rapcsak and two reviewers for insightful suggestions that improved the paper.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.