On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n–2+ [lgn], andW _k (n) = n + (k–1)lg n +O(1) for all fixed k 3. In this paper we studyW _k (n), the minimax complexity of selecting thek largest, when tests of the form Isx _i the median of {x _i ,x _j ,x _t }? are also allowed. It is proved thatW₂(n) =n–2+ [lgn], andW _k (n) =n + (k–1)lg₂ n +O(1) for all fixedk3.This research was supported in part by the National Science Foundation under Grant No. DCR-8308109.     

On the largest feedback linearizable subsystem

A feedback invariant set of integers is associated with any nonlinear multivariable system which is linear with respect to the inputs: it is shown to be the set of controllability indices of the largest feedback linearizable subsystem, i.e. the largest subsystem which can be made locally linear and controllable by means of nonsingular feedback transformations.     

On the largest input-output linearizable subsystem

Feedback input-output linearization is considered in this paper. The main result provides the necessary and sufficient conditions to determine the largest dimension of a linear subsystem achievable by a suitable coordinate change after an input-output linearization feedback has been applied. A systematic method to find the desired coordinate change is also given in this paper     

On graphs with the third largest number of maximal independent sets

Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined.     

The median problem with congestion

The median problem has been generalized to include queueing-like congestion of facilities (which are assumed to have finite numbers of servers). In one statement of the generalizations, a closest available server is assumed to handle each service request. More general server assignment policies are admissable. The objective is to minimize the steady state expected travel time associated with a random service request. It is shown that, under suitable conditions, at least one set of optimal locations exists solely on the nodes of the network. It is also shown that this result has a direct relationship to the hypercube queueing model.     

Computing largest empty circles with location constraints

LetQ = {q₁, q₂,..., q_n} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq _i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.⁽⁹⁾ In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ?O(n ²).     

On selecting a low-order model using the dominant mode concept

A technique for selecting a low-order system to approximate a high-order model has been suggested by Davison [2]. A critical component in this technique is the criterion used to select the most appropriate order and modes for the low-order approximation. Criteria have been discussed and analyzed by Mahapatra [5], [6], Rao, Lamba, and Rao [7], and Elrazaz and Sinha [3]. In this note we overcome deficiencies in the criteria that have been proposed and we introduce a new criterion which is rigorously justified. The criterion we suggest is also applicable when eigenvalues of the system are nonreal.     

On coping with real-time software dynamic inconsistency by built-in tests

In real-time systems, dynamic inconsistencies of software are hardly detected, diagnosed and handled. A built-in test (BIT) method is developed to cope with software dynamic inconsistency. BIT is defined as a new kind of software testing which is explicitly described in object-oriented source code as member functions. BITs can be activated at any designed moment at run-time to detect, diagnose and handle software dynamic inconsistencies. This paper develops a new approach to cope with software dynamic inconsistencies at run-time by BITs. In this paper, the concept of BITs is introduced. The standard structures which incorporate BITs into conventional object-oriented software are analysed. Reuse methodologies for BITs in OO software are developed at object and system levels. A case study is provided for showing how to create BIT and how to inherit and reuse BITs in OO programming. Methods for incorporating BITs into OO software at object, class and system levels are provided. An approach to dynamic inconsistency control by BITs is developed. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the robustness of median sampling in noisy evolutionary optimization

Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics,which have wide applications in various practical optimization problems.In these prob...     

On multistage ranked set sampling for distribution and median estimation

A variation of ranked set sampling (RSS), multistage RSS (MSRSS), is investigated for the estimation of the distribution function and some of its quantiles, in particular the median. It is shown that this method is significantly more efficient than simple random sampling (SRS). The method becomes more and more effective as the number of stages r increases. Two estimators of the median based on MSRSS are proposed and compared to the sample median obtained by SRS.     

On statistical comparison of two diagnostic tests

A one-sample hypothesis testing method is presented for comparing the accuracy of two diagnostic tests. Costs and inconveniences related to the false positive and false negative diagnostic test results, to the extent that they are quantifiable, are considered as measures of the importance of avoiding misclassification. The use of the proposed method is illustrated by comparing the effectiveness of aspiration biopsy cytology and frozen section in detecting malignant thyroid disease.     

基于四分法噪声检测的开关中值滤波算法

为了精确的检测出图像中的脉冲噪声并滤除,提出一种差分四分法的开关中值滤波算法.该算法对噪声检测窗口内像素按灰度值大小排序,通过差分方法划分出高、低阶信号块和高,低阶噪声块4部分.当待测像素属于高,低阶信号块时视其为信号点,否则,根据噪声块与信号块内像素比例关系确定其为噪声点或可能噪声点,若为可能噪声点,则扩展检测窗口重新检测.对于噪声点,基于其邻域噪声密度自适应的确定滤波窗口,取滤窗内信号点的中值作为滤波输出.实验证明该算法对脉冲噪声有很强的抑制作用.     

On certain computable tests and componentwise error bounds

Improved forms of the existence and uniqueness tests due to Pandian are given and are related to results due to Moore and Kioustelidis and to Shen and Neumaier.     

Comment on "On selecting a low-order model using the dominant mode concept"

In the above-mentioned paper [1], the authors presented a criterion for selecting the order of a low-order system to approximate a high-order model. Their criterion is very similar to what has been presented before in [2] and [3]. The authors claimed that the extension to handle systems with complex eigenvalues [3] is incorrect. Also, they used examples to show the superiority of their criterion. In this comment, it will be demonstrated that their claims are not absolutely correct.     

Star p-hub median problem with modular arc capacities

We consider the hub location problem, where p hubs are chosen from a given set of nodes, each nonhub node is connected to exactly one hub and each hub is connected to a central hub. Links are installed on the arcs of the resulting network to route the traffic. The aim is to find the hub locations and the connections to minimize the link installation cost. We propose two formulations and a heuristic algorithm to solve this problem. The heuristic is based on Lagrangian relaxation and local search. We present computational results where formulations are compared and the quality of the heuristic solutions are tested.     

Interpolating datasets with trends: A modified median polish approach

This article investigates an alternative method to deal with data sets in the presence of trends. Median polish kriging (MPK) was introduced as an alternative solution to universal kriging or intrinsic random functions of order k (IRF-k) for estimation in the presence of trends. The maps obtained using the original MPK algorithm show banding artefacts which do not appear in the reference data set. A modified version of MPK was introduced to attempt to remove the banding artefacts. The results confirm the improvement in quality of estimate using the modified version of MPK (called MPKm), which takes into account the problems of clustered samples and boundary effect associated with the re-addition of the trend along bands. The variation introduced in the median polish algorithm proved to be satisfactory in eliminating the artefacts.     

Learning with globally predictive tests

We introduce a new bias for rule learning systems. The bias only allows a rule learner to create a rule that predicts class membership if each test of the rule in isolation is predictive of that class. Although the primary motivation for the bias is to improve the understandability of rules, we show that it also improves the accuracy of learned models on a number of problems. We also introduce a related preference bias that allows creating rules that violate this restriction if they are statistically significantly better than alternative rules without such violations. Michael J. Pazzani, Ph.D.: He is a Full Professor and Chair in the Department of Information and Computer Science at the University of California, Irvine. He obtained his bachelors degree from the University of Connecticut in 1980 and his Ph. D. from University of California, Los Angles in 1987. His research interests are in machine learning, cognitive modeling and information access. He has published over 100 research papers and 2 books. He has served on the Editorial Board of the Machine Learning and the Journal of Artificial Intelligence Research.