We introduce and investigate in multiclass setting an efficient classifier which partitions the training data by means of multidimensional parallelepipeds called boxes. We show that multiclass classification problem at hand can be solved by combining the heuristic minimum clique cover approach and the k-nearest neighbor rule. Our algorithm is motivated by an algorithm for partitioning a graph into a minimal number of cliques. The main advantage of a new classifier called Box classifier is that it optimally utilizes the geometrical structure of the training set by reducing the 1-class classification problem to a single nearest neighbor problem. We discuss computational complexity of the proposed Box classifier. The extensive experiments performed on the simulated and real data from UCI Machine Learning Repository for binary and multiclass problems show that in almost all cases the Box classifier performs significantly better than k-NN, SVM and decision trees.

This paper explores the supervised pattern recognition problem based on feature partitioning. This formulation leads to a new problem in computational geometry. The supervised pattern recognition problem is formulated as an heuristic good clique cover problem satisfying the k-nearest neighbors rule. First it is applied a heuristic algorithm for partitioning a graph into a minimal number of cliques. Next cliques are merged using the k-nearest neighbors rule. An important advantage of this approach is the decomposition of a problem involving l classes into l optimization problems involving a single class. The computational complexity of the method, computational procedures, and classification rules are discussed. A geometrical interpretation of the solution is also given. Using the proposed approach, the geometrical structure of the training set is utilized in the best possible way.

Abstract Bacterium genome plasticity can efficiently be studied by the long‐range polymerase chain reaction (LR‐PCR) technique: genomes of different strains are split into hundreds of short segments which, after LR‐PCR amplification, are used to sketch profiles. The segments have to: (1) cover the entire genome; (2) overlap each other; and (3) be of nearly identical size. This paper addresses the problem of finding a list of segments satisfying these constraints ‘as much as possible’. Two algorithms based on dynamic programming approach are presented. They differ on the optimization criteria for measuring the quality of the covering. The first considers the maximal deviation of the segment lengths relatively to an ideal length. The second automatically finds a segment length that minimizes the maximal deviation. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. Bacterium genome plasticity can efficiently be studied by long-range PCR: genomes of different strains are split into hundreds of short segments which, after LR-PCR amplification, are used to sketch profiles. The segments have : (1) to cover the entire genome, (2) to overlap each other, and (3) to be of nearly identical size. We address the problem of finding a list of segments satisfying these constraints "as much as possible". Two algorithms based on dynamic programming approach are presented. They differ on the optimization criteria for measuring the quality of the covering. The first one considers the maximal deviation of the segment lengths relatively to an ideal length. The second one automatically finds a segment length which minimizes the maximal deviation.

Abstract For the Protein Threading Problem (PTP) we propose a network‐flow like formulation. We also show its equivalence with a generalization of the shortest path problem on a graph with a very particular structure. The underlying Mixed Integer Programming (MIP) model proves to be very appropriate for the PTP—large real‐life instances have been solved much faster by using only the MIP solver CPLEX instead of a known special‐purpose branch and bound algorithm. The properties of the MIP model permit a decomposition of the main problem into a large number of subproblems (tasks). We show that a branch and cut strategy can be efficiently applied for solving these tasks in a parallel manner, which leads to a significant reduction in the total running time. Computational experiments with large problem instances are presented. Copyright © 2004 John Wiley & Sons, Ltd.

This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These models allow for an efficient decomposition and for the application of a parallel branch-and-cut algorithm, significantly reducing the running time. The efficiency of our approach has been confirmed by extensive computational experiments.

For 2D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time on a parallel machine. We consider uniform dependency computations tiled so that (at least) one of the tile boundaries is parallel to the domain boundaries. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary. Our results are based on the BSP model, which assures the portability of the results. Our predictions are justified on a sequence global alignment problem specialized to similar sequences using Fickett's k-band algorithm, for which our optimal semi-oblique tiling yields an improvement of a factor of 2.5 over orthogonal tiling. Our optimal solution requires a block-cyclic distribution of tiles to processors. The best one can obtain with only block distribution (as many authors require) is three times slower. Furthermore, our best running time is within 10 percent of the "predicted theoretical peak" performance of the machine!.

For 2-D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time under the BSP model. We consider uniform dependency computations, tiled so that (at least) one of the tile boundaries is parallel to the domain boundary. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary.

We discuss in this paper the problem of finding the optimal tiling transformation of three-dimensional uniform recurrences on a two-dimensional torus/grid of distributed-memory general-purpose machines. We show that even for the simplest case of recurrences which allows for such transformation, the corresponding problem of minimizing the total running time is a non-trivial non-linear integer programming problem. For the later we derive an O(1) algorithm for finding a good approximation solution. The theoretical evaluations and the experimental results show that the obtained solution approximates the original minimum sufficiently well in the context of the considered problem. Such analytical results are of obvious interest and can be successfully used in parallelizing compilers as well as in performance tuning of parallel codes.