An implementation of logical analysis of data

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems     

Optimal coteries for rings and related networks

Summary Let a distributed system be represented by a graphG=(V, E), whereV is the set of nodes andE is the set of communication links. A coterie is defined as a family,C, of subsets ofV such that any pair of subsets inC has at least one node in common and no subset inC contains any other subset inC. Assuming that each nodev _i V (resp. linke _j E) is operational with probabilityp _i (resp.r _j ), the availability of a coterie is defined as the probability that the operational nodes and links ofG connect all nodes in at least one subset in the coterie. Although it is computationally intractable to find an optimal coterie that maximizes availability for general graphG, we show in this paper that, ifG is a ring, either a singleton coterie or a 3-majority coterie is optimal. Therefore, for any ring, an optimal coterie can be computed in polynomial time. This result is extended to the more general graphs, in which each biconnected component is either an edge or a ring. Toshihide Ibaraki received the B.E., M.E., and Dr. E. degrees from Kyoto University, in 1963, 1965 and 1970, respectively. Since 1969, he has been with the Department of Applied Mathematics and Physics, Kyoto University, except for two and a half years from 1983 to 1985, during which time he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is a professor of Kyoto University. He has held a number of visiting appointments with University of Illinois, University of Waterloo, Simon Fraser University, Rutgers University, and others. He is the author of Enumerative Approaches to Combinatorial Optimization, Baltzer AG., a coauthor of Resource Allocation Problems: Algorithmic Approaches, MIT Press, and the author of several books in Japanese, including Algorithms and Data Structures, Shoukohdou. His interest includes algorithms, optimization, computational complexity and their applications. Hiroshi Nagamochi was born in Tokyo, on January 1, 1960. He received the B.A., M.E. and D.E. degrees from Kyoto University, in 1983, in 1985 and in 1988, respectively. From 1988 to 1990, he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is an Associate Professor in the Department of Applied Mathematics and Physics at Kyoto University. His research interests include network flow problems and graph connectivity problems. Dr. Nagamochi is a member of the Operations Research Society of Japan and the Information Processing Society. Tsunehiko Kameda received the B.E. and M.E. degrees from the University of Tokyo in 1961 and 1963, respectively, and the Ph.D. degree from Princeton University in 1968. From 1967 to 1980, he was with the Department of Electrical Engineering, University of Waterloo. Since 1981, he has been with Simon Fraser University, Burnaby, British Columbia, Canada, where he is a Professor of Computing Science and is the Director of Computer and Communications Research Laboratory. He has held a number of visiting appointments with Universities of Erlangen-Nürnberg, Bonn, Frankfurt, and Braunschweig, and Gesellschaft für Mathematik und Datenverarbeitung, all in Germany, and also with Kyoto University, Japan. Dr. Kameda is a member of the ACM. He has co-authored three books: Einführung in die Codierungstheorie, Bibliographisches Institut, Distributed Algorithms, Kindai Kagaku-Sha, and A Probabilistic Analysis of Test Response Compaction, IEEE Press. His current research interests include database systems, combinatorial algorithms, distributed computing, ATM networks, and random testing of VLSI circuits.This work was supported in part by Grant-in-Aid from the Ministry of Education, Science and Culture of Japan, and in part by grants from the Natural Sciences and Engineering Research Council of Canada, and the Advanced Systems Institute of British Columbia.