Logical regularities in pattern recognition (Parametric Approach)

The search for logical regularities of classes in the recognition by precedents problems and the use of logical regularities for solving recognition and prediction problems are considered. Logical regularities of classes are defined as conjunctions of one-place predicates that determine the membership of a value of a feature in a certain interval of the real axis. The conjunctions are true on the subsets of reference objects of a certain class and are optimal. Various optimality criteria are considered and the problem of finding logical regularities is formulated as an integer programming problem. A qualitative analysis of these problems is performed. Models for evaluating estimates on the basis of systems of logical regularities are considered. Modifications of linear decision rules for finding estimates of how close the reference objects are to classes are proposed that are based on the search for the maximum gap. Approximations of logical regularities of classes by smooth functions is proposed. The concept of the dynamic logical regularity of classes is introduced, an algorithm for finding dynamic logical regularities is proposed, and a prediction method is developed.     

On the construction of irredundant coverings of an integer matrix

New estimates are derived for the computational complexity of the problem of constructing irredundant coverings of an integer matrix (search for maximal conjunctions of a special logical function).     

Disjoint clique cutsets in graphs without long holes

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

模糊推理全蕴涵算法及其还原性

模糊推理是模糊控制的逻辑基础,然而通用的模糊推理CRI算法却缺乏严格的逻辑依据,近期问世的模糊推理全蕴涵三I算法有效地改进了CRI算法。本文研究了全蕴涵三I算法的一般计算公式及其还原性问题,并且得到了一些新的算法,也提出了一些新的观点,文献中已有的结果大多数是本文结果的特例。从而为模糊推理提供了一种新方法。     

On the Solution of Min-sum-min Problems

One class of min-sum-min problems is discussed in the paper. Min-sum-min problems appear in a natural way in many applications (e.g., in cluster analysis, pattern recognition, classification theory etc.). Like min-max-min problems, min-sum-min problems represent a very important family of nonsmooth problems. Problems of this type can be treated by means of the existing tools of Nonsmooth Analysis. However, most of algorithms available provide a local minimizer only, since they are based on necessary conditions which are of local nature. In the paper it is proved that the original problem can be reduced to the problem of minimizing a finite number of sum-functions. A necessary condition for a global minimum and a sufficient condition for a local minimum are stated. The necessary condition is of nonlocal nature. An algorithm (so-called Exchange algorithm) for finding points, satisfying necessary conditions, is described. An ɛ-Exchange algorithm is formulated, allowing, in principle, to escape from a ‘shallow’ local minimizer. An example is presented to illustrate the results and algorithms. An application of the proposed algorithms to solving one clustering problem is also given. Numerical results are provided.AMS Subject Classification:90C30, 49J40.     

Robust Algorithms for the Stable Set Problem

The stable set problem is to find in a simple graph a maximum subset of pairwise non-adjacent vertices. The problem is known to be NP-hard in general and can be solved in polynomial time on some special classes, like cographs or claw-free graphs. Usually, efficient algorithms assume membership of a given graph in a special class. Robust algorithms apply to any graph G and either solve the problem for G or find in it special forbidden configurations. In the present paper we describe several efficient robust algorithms, extending some known results.     

The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard,yet disconnectedness is manageable

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.     

Formalization of a synthesis problem and methods for its solution

A formal formulation is proposed for the synthesis problem of finding objects with certain properties described only by a collection of precedents. A key feature of this formalization is that it is closely related to the pattern recognition theory. A general approach to solving the synthesis problem is described, and particular solution methods are presented in two important cases. For this purpose, a new recognition method is proposed that exhibits a high speed as applied to the data of the structure under study. The performance of the methods is demonstrated on actual data.     

在两循环矩阵类中求解线性方程组反问题的快速算法

本文利用多项式最大公因式 ,给出了线性方程组的反问题在 r-循环矩阵类和对称 r-循环矩阵类中有唯一解的充要条件 ,进而得到线性方程组在 r循环矩阵类和对称 r-循环矩阵类中的反问题求唯一解的算法 .最后给出了应用该算法的数值例子 .     

Supervised fuzzy pattern recognition

This paper is devoted to the problem of supervised fuzzy pattern recognition. The cases with non-fuzzy and fuzzy labels are considered. Based on the properties of linearly separable fuzzy classes, some algorithms are proposed for building matching functions of these classes. All algorithms are computer oriented and can be implemented for the automatic recognition of fuzzy patterns.     

Estimation of dependences based on Bayesian correction of a committee of classification algorithms

Estimation of dependence of a scalar variable on the vector of independent variables based on a training sample is considered. No a priori conditions are imposed on the form of the function. An approach to the estimation of the functional dependence is proposed based on the solution of a finite number of special classification problems constructed on the basis of the training sample and on the subsequent prediction of the value of the function as a group decision. A statistical model and Bayes’ formula are used to combine the recognition results. A generic algorithm for constructing the regression is proposed for different approaches to the selection of the committee of classification algorithms and to the estimation of their probabilistic characteristics. Comparison results of the proposed approach with the results obtained using other models for the estimation of dependences are presented.     

Algorithm for choosing conjunctions for logical recognition methods

A new family of recognition algorithms for problems with binary information is constructed. A natural method is proposed for ordering conjunctions used in pattern recognition problems in the standard formulation and with binary features.     

Convergent Lagrangian and domain cut method for nonlinear knapsack problems

The nonlinear knapsack problem, which has been widely studied in the OR literature, is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to separable nondecreasing constraints. In this paper we develop a convergent Lagrangian and domain cut method for solving this kind of problems. The proposed method exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the finding of an optimal exact solution to the primal problem. The algorithm is first motivated and developed for singly constrained nonlinear knapsack problems and is then extended to multiply constrained nonlinear knapsack problems. Computational results are presented for a variety of medium- or large-size nonlinear knapsack problems. Comparison results with other existing methods are also reported.     

Generalized multivalued nonlinear quasivariational inclusions

In this paper, we introduce and study a few classes of generalized multivalued nonlinear quasivariational inclusions and generalized nonlinear quasivariational inequalities, which include many classes of variational inequalities, quasivariational inequalities and variational inclusions as special cases. Using the resolvent operator technique for maximal monotone mapping, we construct some new iterative algorithms for finding the approximate solutions of these classes of quasivariational inclusions and quasivariational inequalities. We establish the existence of solutions for this generalized nonlinear quasivariational inclusions involving both relaxed Lipschitz and strongly monotone and generalized pseudocontractive mappings and obtain the convergence of iterative sequences generated by the algorithms. Under certain conditions, we derive the existence of a unique solution for the generalized nonlinear quasivariational inequalities and obtain the convergence and stability results of the Noor type perturbed iterative algorithm. The results proved in this paper represent significant refinements and improvements of the previously known results in this area.     

Dual approaches to finite element model updating

The problem of finding the least change adjustment to a stiffness matrix modeled by finite element method is considered in this paper. Desired stiffness matrix properties such as symmetry, sparsity, positive semidefiniteness, and satisfaction of the characteristic equation are imposed as side constraints of the constructed optimal matrix approximation for updating the stiffness matrix, which matches measured data better. The dual problems of the original constrained minimization are presented and solved by subgradient algorithms with different line search strategies. Some numerical results are included to illustrate the performance and application of the proposed methods.     

Metrics of algebraic closures in pattern recognition problems with two nonoverlapping classes

It is shown that, in the pattern recognition problem with two nonoverlapping classes, the matrices of estimates of the object closeness are described by a metric. The transition to the algebraic closure of the model of recognizing operators of finite degree corresponds to the application of a special transformation of this metric. It is proved that the minimal degree correct algorithm can be found as a polynomial of a special form. A simple criterion for testing classification implementations is obtained.     

Iterative methods for solving proximal split minimization problems

In this paper, we propose two iterative algorithms for finding the minimum-norm solution of a split minimization problem. We prove strong convergence of the sequences generated by the proposed algorithms. The iterative schemes are proposed in such a way that the selection of the step-sizes does not need any prior information about the operator norm. We further give some examples to numerically verify the efficiency and implementation of our new methods and compare the two algorithms presented. Our results act as supplements to several recent important results in this area.     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

Loop invariants,exploration of regularities,and mathematical games

Loop invariants are assertions of regularities that characterize the loop components of algorithms. They are fundamental components of computerprograms verification, but their relevance goes beyond verification—they can be significantly utilized for algorithm design and analysis. Unfortunately, they are only modestly introduced in the teaching of programming and algorithms. One reason for this is an unjustified notion that loop invariants are ‘tied to formality’, hard to illustrate, and difficult to comprehend. In this paper a novel approach is presented for illustrating on a rather intuitive level the significance of loop invariants. The illustration is based on mathematical games, which are attractive examples that require the exploration of regularities via problemsolving heuristics. Throughout the paper students' application of heuristics is described and emphasis is placed on the links between loop invariants, heuristic search activities, recognition of regularities and design and analysis of algorithms.