A new distance metric on strings computable in linear time

We describe a new metric for sequence comparison that emphasizes global similarity over sequential matching at the local level. It has the advantage over the Levenshtein metric that strings of lengths n and m can be compared in time proportional to n + m instead of nm. Various mathematical properties of the metric are established.     

On the size of the alphabet and the subword complexity of square-free DOI languages

A word is called square-free if it does not contain a subword of the form αα where α is a nonempty word. A language is called square-free if it consists of square-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which for a positive integer n assigns the number of different subwords of lenght n occurring in words of K. It is known that if a DOL language K is square-free then, for all n, π_K(n) ≤ r n log₂ for some positive integer r. We demonstrate that there exists a square-free DOL language K on four letters such that, for all n, π_K(n) ≥ r n log₂ for some positive real p. This turns out to be the best lower bound on the size of the alphabet needed for a square-free DOL language to have the number of subwords of order nlog_nn     

Robust output feedback time optimal decomposed controllers for linear systems via moving horizon estimation

This paper studies the robust output feedback time optimal control (TOC) problem for linear discrete-time systems with state and input constraints. Bounded state disturbances are assumed. The moving horizon estimation (MHE) technique combined with a Luenberger observer is used to design a state estimator with which the state estimation error converges to and remains in some disturbance invariant set. A novel approach is proposed to reduce the computational complexity of TOC, in which the terminal controller comprises several predetermined local linear feedback laws, resulting in a large terminal set. Starting from this relatively large terminal set, a large domain of attraction of the proposed TOC controller can be obtained by using a short horizon, which consequently leads to a low on-line computational effort. A correction term, the output of the observer subtracted from the output of the plant and then multiplied by a design matrix, is added to the TOC controller, which aims at further correcting estimates of the state based on the present estimation error. Furthermore, by formulating a suitable cost function, as time evolves the TOC controller reaches the desired controller to obtain a good asymptotical behavior. A case study is used to illustrate the proposed approach.     

Approximation with the output of linear control systems

In this paper we give a new proof that for controllable and observable linear systems every L²[0,T] function can be approximated in the L²[0,T] sense with an output function generated by an L²[0,T] input function. We also give a new characterization of how continuous functions on [0,T] are uniformly approximated by an output generated by a continuous input function. The relative degree of the transfer function of the system determines those functions that can be approximated. We further show that if the initial data is allowed to vary then every continuous function is uniformly approximated by outputs generated by continuous functions.     

Sorting in linear expected time

A new sorting algorithm, Double Distributive Partitioning, is introduced and compared against Sedgewick's quicksort. It is shown that the Double Distributive Partitioning algorithm runs, for all practical purposes, inO(n) time for many distributions of keys. Furthermore, the combined number of comparisons, additions, and assignments required to sort by the new method on these distributions is always less than quicksort.     

Solving linear program as linear system in polynomial time

A physically concise polynomial-time iterative-cum-non-iterative algorithm is presented to solve the linear program (LP) $Min{c}^{t}x\text{subject to}Ax=b,x\ge 0$. The iterative part–a variation of Karmarkar projective transformation algorithm–is essentially due to Barnes only to the extent of detection of basic variables of the LP taking advantage of monotonic convergence. It involves much less number of iterations than those in the Karmarkar projective transformation algorithm. The shrunk linear system containing only the basic variables of the solution vector $x$ resulting from $Ax=b$ is then solved in the mathematically non-iterative part. The solution is then tested for optimality and is usually more accurate because of reduced computation and has less computational and storage complexity due to smaller order of the system. The computational complexity of the combination of these two parts of the algorithm is polynomial-time $O\left(n^3\right)$. The boundedness of the solution, multiple solutions, and no-solution (inconsistency) cases are discussed. The effect of degeneracy of the primal linear program and/or its dual on the uniqueness of the optimal solution is mentioned. The algorithm including optimality test is implemented in Matlab which is found to be useful for solving many real-world problems.     

Coloring Meyniel graphs in linear time

A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. We present a linear-time algorithm that colors optimally the vertices of a Meyniel graph and finds a clique of maximum size.     

Planar graph bipartization in linear time

For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k.     

Constructing suffix arrays in linear time

The time complexity of suffix tree construction has been shown to be equivalent to that of sorting: O(n) for a constant-size alphabet or an integer alphabet and O(nlogn) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of O(nlogn) even for a constant-size alphabet.

In this paper we present a linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches that of constructing suffix trees.     

Piecewise linear output measures in DEA (third revision)

It is assumed in the standard DEA model that the aggregate output (input) is a pure linear function of each output (input). This means, for example, that if DMU _j1$j_1$ generates twice as much of an output as does another DMU _j2$j_2$, then the former is credited with having created twice as much value  . In many situations, however, linear pricing (_μryrj)$({\mu }_r{y}_{\mathit{rj}})$ may not adequately reflect differences in value created from one DMU to another. In this paper, a generalization of the DEA methodology is presented that incorporates piecewise linear functions of factors. We deal specifically with those situations where for certain outputs in an input-oriented model, the weight function f(_yrj)$f(y_{\mathit{rj}})$ is described by either a non-increasing or non-decreasing set of multipliers for larger amounts of the factor. We refer to such a variable r as exhibiting diminishing marginal value (DMV) or increasing marginal value   (IMV). The DMV/IMV phenomenon is common in many for-profit applications. For example, in the case that _yrj$y_{\mathit{rj}}$ is the amount of a consumer product r generated by DMU j  , and _μr${\mu }_r$ is the price of that product, it may well be that the market will force lower prices if greater amounts of that product are generated; discounts automatically lead to this DMV situation. Such a phenomenon can arise as well in not-for-profit settings, and we examine such a situation based on earlier work by Cook et al. [Cook, W.D., Roll, Y., Kazakov, A., 1990. A DEA model for measuring the relative efficiency of highway maintenance patrols. INFOR 28 (2), 113–124].     

Detecting perfect powers in essentially linear time

This paper (1) gives complete details of an algorithm to compute approximate th roots; (2) uses this in an algorithm that, given an integer , either writes as a perfect power or proves that is not a perfect power; (3) proves, using Loxton's theorem on multiple linear forms in logarithms, that this perfect-power decomposition algorithm runs in time .

     

Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

Searching for K3,3in linear time

It is shown that the search version of the subgraph homeomorphism problem for K_3,3 can be solved in time linear in the number of vertices of an arbitrary graph. This improves upon a previous result of Asano [1], who described a linear-time algorithm for the decision version of the problem and a quadratic-time algorithm for the search problem.     

Stable minimum space partitioning in linear time

In the stable0–1 sorting problem the task is to sort an array ofn elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe gave an algorithm which solves this problem inO(n log*n) time and constant extra space. We show that by a modification of their method the stable0–1 sorting is possible inO(n) time andO(1) extra space. Stable three-way partitioning can be reduced to stable0–1 sorting. This immediately yields a stable minimum space quicksort, which sorts multisets in asymptotically optimal time with high probability.     

positivity in time dependent linear transport theory

We present methods using positive semigroups and perturbation theory in the application to the linear Boltzmann equation. Besides being a review, this paper also presents generalizations of known results and develops known methods in a more abstract setting.In Section 1 we present spectral properties of the semigroup operatorsW _a(t) of the absorption semigroup and its generatorT _a. In Section 2 we treat the full semigroup (W(t);t0) as a perturbation of the absorption semigroup. We discuss part of the problems (perturbation arguments and existence of eigenvalues) which have to be solved in order to obtain statements about the large time behaviour ofW(·). In Section 3 we discuss irreducibility ofW(·).In four appendices we present abstract methods used in Sections 1, 2 and 3.     

Triangulating a simple polygon in linear time

We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are the polygon-cutting theorem, which provides us with a balancing scheme, and the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, of our algorithm. The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8700917.