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.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

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.     

Parameterized complexity of control problems in Maximin election

Elections are a central model in a variety of areas. This paper studies parameterized computational complexity of five control problems in the Maximin election. We obtain the following results: constructive control by adding candidates is W[2]-hard with respect to the parameter “number of added candidates”; both constructive and destructive control by adding/deleting voters are W[1]-hard with respect to the parameter “number of added/deleted voters”.     

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.     

Verification of reactive systems via instantiation of Parameterised Boolean Equation Systems

Verification problems for finite- and infinite-state processes, like model checking and equivalence checking, can effectively be encoded in Parameterised Boolean Equation Systems (PBESs). Solving the PBES then solves the encoded problem. The decidability of solving a PBES depends on the data sorts that occur in the PBES. We describe a pragmatic methodology for solving PBESs, viz., by attempting to instantiate them to the sub-fragment of Boolean Equation Systems (BESs). Unlike solving PBESs, solving BESs is a decidable problem. Based on instantiation, verification using PBESs can effectively be done fully automatically in most practical cases. We demonstrate this by solving several complex verification problems using a prototype implementation of our instantiation technique. In addition, practical issues concerning this implementation are addressed. Furthermore, we illustrate the effectiveness of instantiation as a transformation on PBESs when solving verification problems involving systems of infinite size.     

Partially varying coefficient single index proportional hazards regression models

In this paper, the partially varying coefficient single index proportional hazards regression models are discussed. All unknown functions are fitted by polynomial B splines. The index parameters and B-spline coefficients are estimated by the partial likelihood method and a two-step Newton-Raphson algorithm. Consistency and asymptotic normality of the estimators of all the parameters are derived. Through a simulation study and the VA data example, we illustrate that the proposed estimation procedure is accurate, rapid and stable.     

Powers in a class of -strict standard episturmian words

This paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic Sturmian words. In particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of Damanik and Lenz [D. Damanik, D. Lenz, Powers in Sturmian sequences, European J. Combin. 24 (2003) 377–390, doi:10.1016/S0195-6698(03)00026-X], who studied powers in Sturmian words. The key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous Fibonacci word. Our main results are demonstrated via some examples, including the k-bonacci word, a generalization of the Fibonacci word to a k-letter alphabet (k≥2).     

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.     

Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound

The k-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most k different values are decided. It has been shown that any algorithm that solves the k-set agreement problem in synchronous systems that can suffer up to t crash failures requires rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after rounds, where f is the number of actual crashes in a run (0≤f≤t).This paper explores a new direction to solve the k-set agreement problem in a synchronous system. It considers that the system is enriched with base objects (denoted has [m,?]_SA objects) that allow solving the ?-set agreement problem in a set of m processes (m<n). The paper makes several contributions. It first proposes a synchronous k-set agreement algorithm that benefits from such underlying base objects. This algorithm requires rounds, more precisely, rounds, where . The paper then shows that this bound, that involves all the parameters that characterize both the problem (k) and its environment (t, m and ?), is a lower bound. The proof of this lower bound sheds additional light on the deep connection between synchronous efficiency and asynchronous computability. Finally, the paper extends its investigation to the early deciding case. It presents a k-set agreement algorithm that directs the processes to decide and stop by round . These bounds generalize the bounds previously established for solving the k-set agreement problem in pure synchronous systems.     

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.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

Oriented colorings of partial 2-trees

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f(x)f(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth g?3. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.     

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.     

Equitable and equitable list colorings of graphs

A proper k-vertex coloring of a graph is an equitable k-coloring if the sizes of the color classes differ by at most 1. A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most vertices. We prove in this paper that outerplane graphs are equitably k-choosable whenever k≥Δ, where Δ is the maximum degree. Moreover, we discuss equitable colorings of some d-degenerate graphs.     

A modified hybrid projection method for solving generalized mixed equilibrium problems and fixed point problems in Banach spaces

In this paper, we introduce a modified new hybrid projection method for finding the set of solutions of the generalized mixed equilibrium problems and the convex feasibility problems for an infinite family of closed and uniformly quasi-?-asymptotically nonexpansive mappings. Strong convergence theorems are established in a uniformly smooth and strictly convex Banach space which also enjoys the Kadec-Klee property. Our results improve and extend the corresponding results announced by Qin et al. (2010) and many authors.     

Exact solutions for the unsteady rotating flows of a generalized Maxwell fluid with oscillating pressure gradient between coaxial cylinders

This paper deals with the unsteady rotating flow of a generalized Maxwell fluid with fractional derivative model between two infinite straight circular cylinders, where the flow is due to an infinite straight circular cylinder rotating and oscillating pressure gradient. The velocity field and the adequate shear stress are determined by means of the combine of the sequential fractional derivatives Laplace transform and finite Hankel transform. The exact solutions are presented by integral and series form in terms of the generalized G and Mittag-Leffler functions. The similar solutions can be easily obtained for ordinary Maxwell and Newtonian fluids as limiting cases. Finally, the influence of the relaxation time and the fractional parameter on the fluid dynamic characteristics, as well as a comparison between models, is shown by graphical illustrations.     

Linguistic truth-valued lattice-valued propositional logic system ?P(X) based on linguistic truth-valued lattice implication algebra

In the semantics of natural language, quantification may have received more attention than any other subject, and syllogistic reasoning is one of the main topics in many-valued logic studies on inference. Particularly, lattice-valued logic, a kind of important non-classical logic, can be applied to describe and treat incomparability by the incomparable elements in its truth-valued set. In this paper, we first focus on some properties of linguistic truth-valued lattice implication algebra. Secondly, we introduce some concepts of linguistic truth-valued lattice-valued propositional logic system ?P(X), whose truth-valued domain is a linguistic truth-valued lattice implication algebra. Then we investigate the semantic problem of ?P(X). Finally, we further probe into the syntax of linguistic truth-valued lattice-valued propositional logic system ?P(X), and prove the soundness theorem, deduction theorem and consistency theorem.     

Equivalence of rational representations of behaviors

This article deals with the equivalence of representations of behaviors of linear differential systems. In general, the behavior of a given linear differential system has many different representations. In this paper we restrict ourselves to kernel and image representations. Two kernel representations are called equivalent if they represent one and the same behavior. For kernel representations defined by polynomial matrices, necessary and sufficient conditions for equivalence are well known. In this paper, we deal with the equivalence of rational representations, i. e. kernel and image representations that are defined in terms of rational matrices. As the first main result of this paper, we will derive a new condition for the equivalence of rational kernel representations of possibly noncontrollable behaviors. Secondly we will derive conditions for the equivalence of rational representations of a given behavior in terms of the polynomial modules generated by the rows of the rational matrices. We will also establish conditions for the equivalence of rational image representations. Finally, we will derive conditions under which a given rational kernel representation is equivalent to a given rational image representation.