Computational algorithms for censored-data problems using intersection graphs

This article presents methods for finding the nonparametric maximum likelih ood estimate (NPMLE) of the distribution function of time-to-event data. Th e basic approach is to use graph theory (in particular intersection graphs) to simplify the problem. Censored data can be represented in terms of thei r intersection graph. Existing combinatorial algorithms can be used to find the important structures, namely the maximal cliques. When viewed in this framework there is no fundamental difference between right censoring, inter val censoring, double censoring, or current status data and hence the algor ithms apply to all types of data. These algorithms can be extended to deal with bivariate data and indeed there are no fundamental problems extending the methods to higher dimensional data. Finally this article shows how to o btain the NPMLE using convex optimization methods and methods for mixing di stributions. The implementation of these methods is greatly simplified thro ugh the graph-theoretic representation of the data.