Simultaneous Modelling of Survival and Longitudinal Data with an Application to Repeated Quality of Life Measures

In biomedical studies, interest often focuses on the relationship between patients characteristics or some risk factors and both quality of life and survival time of subjects under study. In this paper, we propose a simultaneous modelling of both quality of life and survival time using the observed covariates. Moreover, random effects are introduced into the simultaneous models to account for dependence between quality of life and survival time due to unobserved factors. EM algorithms are used to derive the point estimates for the parameters in the proposed model and profile likelihood function is used to estimate their variances. The asymptotic properties are established for our proposed estimators. Finally, simulation studies are conducted to examine the finite-sample properties of the proposed estimators and a liver transplantation data set is analyzed to illustrate our approaches.     

Two-Stage Estimation in Copula Models Used in Family Studies

In this paper register based family studies provide the motivation for studying a two-stage estimation procedure in copula models for multivariate failure time data. The asymptotic properties of the estimators in both parametric and semi-parametric models are derived, generalising the approach by Shih and Louis (Biometrics vol. 51, pp. 1384–1399, 1995b) and Glidden (Lifetime Data Analysis vol. 6, pp. 141–156, 2000). Because register based family studies often involve very large cohorts a method for analysing a sampled cohort is also derived together with the asymptotic properties of the estimators. The proposed methods are studied in simulations and the estimators are found to be highly efficient. Finally, the methods are applied to a study of mortality in twins.     

Efficient Algorithms for Determining 3-D Bi-Plane Imaging Geometry

Biplane projection imaging is one of the primary methods for imaging and visualizing the cardiovascular system in medicine. A key problem in such a technique is to determine the imaging geometry (i.e., the relative rotation and translation) of two projections so that the 3-D structure can be accurately reconstructed. Based on interesting observations and efficient geometric techniques, we present in this paper new algorithmic solutions for this problem. Comparing with existing optimization-based approaches, our techniques yield better accuracy and have bounded execution time, thus is more suitable for on-line applications. Our techniques can easily detect outliers to further improve the accuracy.This research was supported in part by NIH under USPHS grant numbers HL52567.     

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.     

On Approximation Ratios of Minimum-Energy Multicast Routing in Wireless Networks

In the broadcasting of ad hoc wireless networks, energy conservation is a critical issue. Three heuristic algorithms were proposed in Wieselthier et al.(2001) for finding approximate minimum-energy broadcast routings: MST(minimum spanning tree), SPT(shortest-path tree), and BIP(broadcasting incremental power). Wan et al.(2001) characterized their performance in terms of approximation ratios. This paper points out some mistakes in the result of Wan et al.(2001), and proves that the upper bound of sum of squares of lengths of the edges in Euclidean MST in unit disk can be improved to 10.86, thus improves the approximation ratios of MST and BIP algorithm.Supported by Natural Science Foundation of China (60223004, 603210022)     

Broadcast Routing with Minimum Wavelength Conversion in WDM Optical Networks

We consider dynamic routing of broadcast connections in WDM optical networks. Given the current network state, we want to find a minimum set of network nodes S such that a broadcast routing using only the nodes in S as wavelength conversion nodes can be found. This ensures that the average conversion delay from the source to all destinations is minimized. We refer to the problem as Broadcast Conversion Node Selection (BCNS) problem. We prove that BCNS has no polynomial-time approximation with performance ratio ln n for < 1 unless NPDTIME(n^{O(log log n)}) where n is the number of vertices in the input graph. We present a greedy approximation algorithm for BCNS that achieves approximation ratio 2+ln n. Simulation results show that the algorithm performs very well in practice, obtaining optimal solutions in most of the cases.     

A Tighter Extra-Resource Analysis of Online Deadline Scheduling

This paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee.A preliminary version of this paper has been accepted by The Australian Theory Symposium on Computing, 2004.This research was supported in part by Hong Kong RGC Grant HKU-7024/01E.     

Feature Selection for Consistent Biclustering via Fractional 0–1 Programming

Biclustering consists in simultaneous partitioning of the set of samples and the set of their attributes (features) into subsets (classes). Samples and features classified together are supposed to have a high relevance to each other which can be observed by intensity of their expressions. We define the notion of consistency for biclustering using interrelation between centroids of sample and feature classes. We prove that consistent biclustering implies separability of the classes by convex cones. While previous works on biclustering concentrated on unsupervised learning and did not consider employing a training set, whose classification is given, we propose a model for supervised biclustering, whose consistency is achieved by feature selection. The developed model involves solution of a fractional 0–1 programming problem. Preliminary computational results on microarray data mining problems are reported.This research work was partially supported by NSF, NIH and AirForce grants.     

The Center Location Improvement Problem Under the Hamming Distance

In this paper, we consider the center location improvement problems under the sum-type and bottleneck-type Hamming distance. For the sum-type problem, we show that achieving an algorithm with a worst-case ratio of O(log |V|) is NP-hard, and for the bottleneck-type problem, we present a strongly polynomial algorithm.     

Clustering of Microarray data via Clique Partitioning

Microarrays are repositories of gene expression data that hold tremendous potential for new understanding, leading to advances in functional genomics and molecular biology. Cluster analysis (CA) is an early step in the exploration of such data that is useful for purposes of data reduction, exposing hidden patterns, and the generation of hypotheses regarding the relationship between genes and phenotypes. In this paper we present a new model for the clique partitioning problem and illustrate how it can be used to perform cluster analysis in this setting.