On the hardness of finding near-optimal multicuts in directed acyclic graphs

Given an edge-weighted (di)graph and a list of source-sink pairs of vertices of this graph, the minimum multicut problem consists in selecting a minimum-weight set of edges (or arcs), whose removal leaves no path from each source to the corresponding sink. This is a well-known NP-hard problem, and improving several previous results, we show that it remains APX-hard in unweighted directed acyclic graphs (DAG), even with only two source-sink pairs. This is also true if we remove vertices instead of arcs.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Makespan minimization on single batch-processing machine via ant colony optimization

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.     

Online computation with advice

We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice is a function, defined by the online algorithm, of the whole request sequence. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b=0 corresponds to the classical online model, and b=⌈log∣A∣⌉, where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones.In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1≤b≤Θ(logn), where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω(log(n)/b) and we present a deterministic online algorithm for MTS with competitive ratio O(log(n)/b). For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k^O(1/b) for any choice of Θ(1)≤b≤logk.     

An LMI approach to minimum sensitivity analysis with application to fault detection

This paper systematically studies the minimum input sensitivity analysis problem. The lowest level of sensitivity of system outputs to system inputs is defined as an H_- index. A full characterization of the H_- index is given, first, in terms of matrix equalities and inequalities, and then in terms of linear matrix inequalities (LMIs), as a dual of the Bounded Real Lemma. A related problem of input observability is also studied, with new necessary and sufficient conditions given, which are necessary for a fault detection system to have a nonzero worst-case fault sensitivity. The above results are applied to the problem of fault detection filter analysis, with numerical examples given to show the effectiveness of the proposed approaches.     

Three-dimensional beta shapes

The Voronoi diagram of a point set has been extensively used in various disciplines ever since it was first proposed. Its application realms have been even further extended to estimate the shape of point clouds when Edelsbrunner and Mücke introduced the concept of α-shape based on the Delaunay triangulation of a point set.In this paper, we present the theory of β-shape for a set of three-dimensional spheres as the generalization of the well-known α-shape for a set of points. The proposed β-shape fully accounts for the size differences among spheres and therefore it is more appropriate for the efficient and correct solution for applications in biological systems such as proteins.Once the Voronoi diagram of spheres is given, the corresponding β-shape can be efficiently constructed and various geometric computations on the sphere complex can be efficiently and correctly performed. It turns out that many important problems in biological systems such as proteins can be easily solved via the Voronoi diagram of atoms in proteins and β-shapes transformed from the Voronoi diagram.     

A class of aggregation functions encompassing two-dimensional OWA operators

In this paper we prove that, under suitable conditions, Atanassov’s K_α operators, which act on intervals, provide the same numerical results as OWA operators of dimension two. On one hand, this allows us to recover OWA operators from K_α operators. On the other hand, by analyzing the properties of Atanassov’s operators, we can generalize them. In this way, we introduce a class of aggregation functions - the generalized Atanassov operators - that, in particular, include two-dimensional OWA operators. We investigate under which conditions these generalized Atanassov operators satisfy some properties usually required for aggregation functions, such as bisymmetry, strictness, monotonicity, etc. We also show that if we apply these aggregation functions to interval-valued fuzzy sets, we obtain an ordered family of fuzzy sets.     

On the complexity of sandpile critical avalanches

In this work, we study The Abelian Sandpile Model from the point of view of computational complexity. We begin by studying the length distribution of sandpile avalanches triggered by the addition of two critical configurations: we prove that those avalanches are long on average, their length is bounded below by a constant fraction of the length of the longest critical avalanche which is, in most of the cases, superlinear. At the end of the paper we take the point of view of computational complexity, we analyze the algorithmic hardness of the problem consisting in computing the addition of two critical configurations, we prove that this problem is P complete, and we prove that most algorithmic problems related to The Abelian Sandpile Model are NC reducible to it.     

Negative selection algorithms on strings with efficient training and linear-time classification

A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σ^? into “normal” and “anomalous” partitions from a training set S containing only samples from the “normal” partition. The algorithm generates a set of patterns, called “detectors”, to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as “anomalous”. A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r-chunk and r-contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S⊆Σ^? and parameter r≤? one can construct an automaton whose acceptance behaviour is equivalent to the algorithm’s classification outcome. The resulting runtime is O(|S|?r|Σ|) for constructing the automaton in the training phase and O(?) for classifying a string.     

Data reduction of large vector graphics

Fast algorithm for joint near-optimal approximation of multiple polygonal curves is proposed. It is based on iterative reduced search dynamic programming introduced earlier for the min-εproblem of a single polygonal curve. The proposed algorithm jointly optimizes the number of line segments allocated to the different individual curves, and the approximation of the curves by the given number of segments. Trade-off between time and optimality is controlled by the breadth of the search, and by the numbers of iterations applied.     

Approximation capabilities of multilayer fuzzy neural networks on the set of fuzzy-valued functions

This paper first introduces a piecewise linear interpolation method for fuzzy-valued functions. Based on this, we present a concrete approximation procedure to show the capability of four-layer regular fuzzy neural networks to perform approximation on the set of all d_p continuous fuzzy-valued functions. This approach can also be used to approximate d_∞ continuous fuzzy-valued functions. An example is given to illustrate the approximation procedure.     

Distinct squares in run-length encoded strings

Squares are strings of the form ww where w is any nonempty string. Two squares ww and w^′w^′ are of different types if and only if w≠w^′. Fraenkel and Simpson [Avieri S. Fraenkel, Jamie Simpson, How many squares can a string contain? Journal of Combinatorial Theory, Series A 82 (1998) 112-120] proved that the number of square types contained in a string of length n is bounded by O(n). The set of all different square types contained in a string is called the vocabulary of the string. If a square can be obtained by a series of successive right-rotations from another square, then we say the latter covers the former. A square is called a c-square if no square with a smaller index can cover it and it is not a trivial square. The set containing all c-squares is called the covering set. Note that every string has a unique covering set. Furthermore, the vocabulary of the covering set are called c-vocabulary. In this paper, we prove that the cardinality of c-vocabulary in a string is less than , where N is the number of runs in this string.     

Multi-frequency disturbance rejection via blending control technique for hard disk drives

This paper is concerned with the rejection of multiple narrowband disturbances in hard disk drives (HDDs). Inspired by a control blending idea, the multi-frequency disturbance rejection is formulated as a blending control problem. Each disturbance rejection is accomplished by using the H₂ optimal control method. Based on all H₂ optimal controllers, the blending technique is applied to yield a single controller which is capable of achieving rejection of all disturbances. Rejections of two and three disturbances for a 1.8-inch HDD VCM actuator are taken as application examples in the paper. Simulation and experimental results show that the ultimate controller results in a simultaneous attenuation of disturbances with frequencies higher or lower than the closed-loop system bandwidth. Moreover, the method turns out to be able to lift phase and thus prevent phase margin loss when it is used to deal with disturbances near bandwidth.     

Incremental learning of bidirectional principal components for face recognition

Recently, bidirectional principal component analysis (BDPCA) has been proven to be an efficient tool for pattern recognition and image analysis. Encouraging experimental results have been reported and discussed in the literature. However, BDPCA has to be performed in batch mode, it means that all the training data has to be ready before we calculate the projection matrices. If there are additional samples need to be incorporated into an existing system, it has to be retrained with the whole updated training set. Moreover, the scatter matrices of BDPCA are formulated as the sum of K (samples size) image covariance matrices, this leads to the incremental learning directly on the scatters impossible, thus it presents new challenge for on-line training.In fact, there are two major reasons for building incremental algorithms. The first reason is that in some cases, when the number of training images is very large, the batch algorithm cannot process the entire training set due to large computational or space requirements of the batch approach. The second reason is when the learning algorithm is supposed to operate in a dynamical settings, that all the training data is not given in advance, and new training samples may arrive at any time, and they have to be processed in an on-line manner. Through matricizations of third-order tensor, we successfully transfer the eigenvalue decomposition problem of scatters to the singular value decomposition (SVD) of corresponding unfolded matrices, followed by complexity and memory analysis on the novel algorithm. A theoretical clue for selecting suitable dimensionality parameters without losing classification information is also presented in this paper. Experimental results on FERET and CMU PIE (pose, illumination, and expression) databases show that the IBDPCA algorithm gives a close approximation to the BDPCA method, but using less time.     

Controller certification

A modern problem from aerospace control involves the certification of a large set of potential controllers with either a single plant or a fleet of potential plant systems, with both plants and controllers being MIMO and, for the moment, linear. Experiments on a limited number of controller/plant pairs should establish the stability and a certain level of margin of the complete set. We consider this certification problem for a set of controllers and provide algorithms for selecting an efficient subset for testing. This is done for a finite set of candidate controllers and, at least for SISO plants, for compact infinite set. In doing this, the ν-gap metric will be the main tool. Computational examples are given, including one of certification of an aircraft engine controller. The overarching aim is to introduce truly MIMO margin calculations and to understand their efficacy in certifying stability over a set of controllers and in replacing legacy single-loop gain and phase margin calculations.     

Application of a new multi-agent Hybrid Co-evolution based Particle Swarm Optimisation methodology in ship design

In this paper, a multiple objective ‘Hybrid Co-evolution based Particle Swarm Optimisation’ methodology (HCPSO) is proposed. This methodology is able to handle multiple objective optimisation problems in the area of ship design, where the simultaneous optimisation of several conflicting objectives is considered. The proposed method is a hybrid technique that merges the features of co-evolution and Nash equilibrium with a ε-disturbance technique to eliminate the stagnation. The method also offers a way to identify an efficient set of Pareto (conflicting) designs and to select a preferred solution amongst these designs. The combination of co-evolution approach and Nash-optima contributes to HCPSO by utilising faster search and evolution characteristics. The design search is performed within a multi-agent design framework to facilitate distributed synchronous cooperation. The most widely used test functions from the formal literature of multiple objectives optimisation are utilised to test the HCPSO. In addition, a real case study, the internal subdivision problem of a ROPAX vessel, is provided to exemplify the applicability of the developed method.     

A necessary and sufficient condition for parameter insensitive disturbance-rejection problem with state feedback

In this paper a necessary and sufficient condition for a parameter insensitive disturbance-rejection problem with state feedback which was pointed out as an open problem by Bhattacharyya to be solvable is proved. A constructive algorithm of simultaneously (A,B)-invariant subspaces for a finite-number of linear systems and a relationship between simultaneously (A,B)-invariant subspaces and generalized (A,B)-invariant subspaces play an important role to prove the main result.     

A new approach to robust guaranteed cost control for uncertain multimodeling systems

The guaranteed cost control problem for multimodeling systems with norm bounded uncertainty is investigated. The main contribution in this paper is that a new ?-independent controller is derived by solving the reduced-order slow and fast algebraic Riccati equations (AREs) whose dimension is smaller than the dimension of full-order multiparameter algebraic Riccati equation (MARE). It is shown that if these AREs have a positive definite stabilizing solution then the closed-loop system is quadratically stable and has the cost bound.