Search

The inference of a general Bayesian network has been shown to be an NP-hard problem, even for approximate solutions. Although k-dependence Bayesian (KDB) classifier can construct at arbitrary points (values of k) along the attribute dependence spectrum, it cannot identify the changes of interdependencies when attributes take different values. Local KDB, which learns in the framework of KDB, is proposed in this study to describe the local dependencies implicated in each test instance. Based on the analysis of functional dependencies, substitution-elimination resolution, a new type of semi-naive Bayesian operation, is proposed to substitute or eliminate generalization to achieve accurate estimation of conditional probability distribution while reducing computational complexity. The final classifier, averaged k-dependence Bayesian (AKDB) classifiers, will average the output of KDB and local KDB. Experimental results on the repository of machine learning databases from the University of California Irvine (UCI) showed that AKDB has significant advantages in zero-one loss and bias relative to naive Bayes (NB), tree augmented naive Bayes (TAN), Averaged one-dependence estimators (AODE), and KDB. Moreover, KDB and local KDB show mutually complementary characteristics with respect to variance. [ABSTRACT FROM AUTHOR]

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,...,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity. [ABSTRACT FROM AUTHOR]

Abstract: In comparative genomics, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given genomic maps as sequences of gene markers, the objective of MSR- is to find subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant , a polynomial-time -approximation for MSR- was previously known. In this paper, we show that for any , MSR- is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating MSR- for all . In particular, we show that MSR- is NP-hard to approximate within . From the other direction, we show that the previous -approximation for MSR- can be optimized into a polynomial-time algorithm even if is not a constant but is part of the input. We then extend our inapproximability results to several related problems including CMSR-, -gap-MSR-, and -gap-CMSR-. [Copyright &y& Elsevier]

Abstract: Super-resolution image reconstruction is the process of producing a high-resolution image from a set of low-resolution images of the same scene. For the applications of performing face evaluation and/or recognition from low-resolution video surveillance, in the past, super-resolution image reconstruction was mainly used as a separate preprocessing step to obtain a high-resolution image in the pixel domain that is later passed to a face feature extraction and recognition algorithm. Such three-stage approach suffers a high degree of computational complexity. A low-dimensional morphable model space based face super-resolution reconstruction and recognition algorithm is proposed in this paper. The approach tries to construct the high-resolution information both required by reconstruction and recognition directly in the low dimensional feature space. We show that comparing with generic pixel domain algorithms, the proposed approach is more robust and more computationally efficient. [Copyright &y& Elsevier]

Abstract: Super-resolution image reconstruction produces a high-resolution image from a set of shifted, blurred, and decimated versions thereof. Previously published papers have not addressed the computational complexity of this ill-conditioned large scale problem adequately. In this paper, the computational complexity of MAP-based multiframe super-resolution algorithms is studied, and a new fast algorithm, as well as methods for parallel image reconstruction is also presented. The proposed fast algorithm splits the multiple input low-resolution images into several subsets according to their translation relations, and then applies normal MAP algorithm to each subset, the reconstructed images are processed subsequently at a successive level until the desired resolution is achieved. Experiment results are also provided to demonstrate the efficiency of the proposed techniques. [Copyright &y& Elsevier]