A weighted polynomial regression method for local fitting of spatial data

Typically, parametric approaches to spatial problems require restrictive assumptions. On the other hand, in a wide variety of practical situations nonparametric bivariate smoothing techniques has been shown to be successfully employable for estimating small or large scale regularity factors, or even the signal content of spatial data taken as a whole.We propose a weighted local polynomial regression smoother suitable for fitting of spatial data. To account for spatial variability, we both insert a spatial contiguity index in the standard formulation, and construct a spatial-adaptive bandwidth selection rule. Our bandwidth selector depends on the Gearys local indicator of spatial association. As illustrative example, we provide a brief Monte Carlo study case on equally spaced data, the performances of our smoother and the standard polynomial regression procedure are compared.This note, though it is the result of a close collaboration, was specifically elaborated as follows: paragraphs 1 and 2 by T. Sclocco and the remainder by M. Di Marzio. The authors are grateful to the referees for constructive comments and suggestions.     

Rethinking a universal framework in the psychiatric symptom-disorder relationship

Research on disparities in health and services should include a critical examination of how social, cultural, and contextual factors affect the connection between symptoms and psychiatric disorders. Systematic differences in this connection by these factors will mean that clinicians using a universalist approach to disorders may make more diagnostic errors for certain patients (e.g., ethnic minorities, the poor). Based on the literature on normative clinical decision-making, this study tests for whether the effect of specific psychiatric disorders on key symptoms is the same for certain groups of the population. The data come from the National Comorbidity Survey. Conditional probabilities of disorders and symptoms, the elements feeding into clinical decision-making, are calculated and tested for equivalence across various racial/ethnic, educational, income, and gender groups. We find some significant differences in the relation of key symptoms to disorders across groups. These findings should encourage testing relativistic frameworks in diagnostic nosology as a step to improve clinical decision-making and reduce diagnostic and treatment disparities in mental health services.     

Missing at random (MAR) in nonparametric regression - A simulation experiment

The additive model is considered when some observations on x are missing at random but corresponding observations on y are available. Especially for this model, missing at random is an interesting case because the complete case analysis is expected to be no more suitable. A simulation experiment is reported and the different methods are compared based on their superiority with respect to the sample mean squared error. Some focus is also given on the sample variance and the estimated bias. In detail, the complete case analysis, a kind of stochastic mean imputation, a single imputation and the nearest neighbor imputation are discussed.     

Editorial

Ohne Zusammenfassung

---

Editorial

     

The densest <Emphasis Type="Italic">k</Emphasis>-subgraph problem on clique graphs

The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques. M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources. V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821.     

Semi-online scheduling with “end of sequence” information

We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem. The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August 2005 after struggling with illness. D. Ye: Research was supported in part by NSFC (10601048).     

Discovering classes in microarray data using island counts

We present a new biclustering algorithm to simultaneously discover tissue classes and identify a set of genes that well-characterize these classes from DNA microarray data sets. We employ a combinatorial optimization approach where the object is to simultaneously identify an interesting set of genes and a partition of the array samples that optimizes a certain score based on a novel color island statistic. While this optimization problem is NP-complete in general, we are effectively able to solve problems of interest to optimality using a branch-and-bound algorithm. We have tested the algorithm on a 30 sample Cutaneous T-cell Lymphoma data set; it was able to almost perfectly discriminate short-term survivors from long-term survivors and normal controls. Another useful feature of our method is that can easily handle missing expression data.     

An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

On edge orienting methods for graph coloring

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.