The longest common subsequence problem for arc-annotated sequences

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The

Full-size image

problem has recently been introduced in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures and present some new algorithmic and complexity results on the problem. Some of our results answer an open question in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in: Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280] and some others improve the hardness results in [P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999; P.A. Evans, Finding common subsequences with arcs and pseudoknots, in: Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99), in Lecture Notes in Comput. Sci., vol. 1645, 1999, pp. 270–280].     

Mixed-integer sets from two rows of two adjacent simplex bases

In Andersen et al. (Lecture Notes in Computer Science, vol. 4513, Springer, Berlin, pp. 1–15, 2007) we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be obtained from triangles and quadrilaterals. Specifically, when exactly one upper bound on a non-basic variable is introduced, stronger inequalities that can be derived from pentagons involving up to six variables also appear.     

The nonidealness index of rank-ideal matrices

A polyhedron is integral if all its extreme points have 0, 1 components and in this case the matrix M is called ideal. When Q has fractional extreme points, there are different ways of classifying how far M is away from being ideal, through the polyhedral structure of Q. In this sense, Argiroffo, Bianchi and Nasini (2006) [1] defined a nonidealness index analogous to an imperfection index due to Gerke and McDiarmid (2001) [10].In this work we determine the nonidealness index of rank-ideal matrices (introduced by the authors (2008)). It is known that evaluating this index is NP-hard for any matrix. We provide a tractable way of evaluating it for most circulant matrices, whose blockers are a particular class of rank-ideal matrices, thereby following similar lines as done for the imperfection ratio of webs due to Coulonges, Pêcher and Wagler (2009) [7].Finally, exploiting the properties of this nonidealness index, we identify the facets of the set covering polyhedron of circulant matrices, having maximum strength with respect to the linear relaxation, according to a measure defined by Goemans (1995) [9].     

An SQP method for general nonlinear programs using only equality constrained subproblems

In this paper we describe a new version of a sequential equality constrained quadratic programming method for general nonlinear programs with mixed equality and inequality constraints. Compared with an older version [P. Spellucci, Han's method without solving QP, in: A. Auslender, W. Oettli, J. Stoer (Eds), Optimization and Optimal Control, Lecture Notes in Control and Information Sciences, vol. 30, Springer, Berlin, 1981, pp. 123–141.] it is much simpler to implement and allows any kind of changes of the working set in every step. Our method relies on a strong regularity condition. As far as it is applicable the new approach is superior to conventional SQP-methods, as demonstrated by extensive numcrical tests. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A sequentially computable function that is not effectively continuous at any point

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.     

The zoo of tree spanner problems

Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of max-stretch tree spanner problems and of average stretch tree spanner problems.We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems.Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati [On min-max cycle bases, in: P. Eades, T. Takaoka (Eds.), ISAAC, Lecture Notes in Computer Science, vol. 2223, Springer, Berlin, 2001, pp. 116-123; On finding cycle bases and fundamental cycle bases with a shortest maximal cycle, Inform. Process. Lett. 88(4) (2003) 155-159] in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2-?, instead of only according to Peleg and Reshef [A variant of the arrow distributed directory with low average complexity, in: J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), ICALP, Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, 1999, pp. 615-624].     

On generalizing Takahashi’s nonconvex minimization theorem

We present a simple proof of vectorial Takahashi’s nonconvex minimization theorem based on Gopfert, Tammer and Zalinescu [A. Gopfert, C. Tammer, C. Zalinescu, On the vectorial Ekeland’s variational principle and minimal points in product spaces, Nonlinear Anal. 39 (2000) 909–922; C. Tammer, A variational principle and a fixed point theorem, in: System Modelling and Optimization (Compiegne, 1993), in: Lecture Notes in Control and Inform. Sci., vol. 197, Springer, London, 1994, pp. 248–257].     

Two applications of relative difference sets: Difference triangles and negaperiodic autocorrelation functions

The well-known difference sets have various connections with sequences and their correlation properties. It is the purpose of this note to give two more applications of the (not so well known) relative difference sets: we use them to construct difference triangles (based on an idea of A. Ling) and we show that a certain nonexistence result for semiregular relative difference sets implies the nonexistence of negaperiodic autocorrelation sequences (answering a question of Parker [Even length binary sequence families with low negaperiodic autocorrelation, in: Applied Algebra, Algebraic Algorithms and Error-correcting Codes, Melbourne, 2001, Lecture Notes in Computer Science, vol. 2227, Springer, Berlin, 2001, pp. 200-209.]).     

Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.     

Applications of the complexity space to the General Probabilistic Divide and Conquer Algorithms

Schellekens [M. Schellekens, The Smyth completion: A common foundation for denotational semantics and complexity analysis, in: Proc. MFPS 11, in: Electron. Notes Theor. Comput. Sci., vol. 1, 1995, pp. 535-556], and Romaguera and Schellekens [S. Romaguera, M. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311-322] introduced a topological foundation to obtain complexity results through the application of Semantic techniques to Divide and Conquer Algorithms. This involved the fact that the complexity (quasi-metric) space is Smyth complete and the use of a version of the Banach fixed point theorem and improver functionals. To further bridge the gap between Semantics and Complexity, we show here that these techniques of analysis, based on the theory of complexity spaces, extend to General Probabilistic Divide and Conquer schema discussed by Flajolet [P. Flajolet, Analytic analysis of algorithms, in: W. Kuich (Ed.), 19th Internat. Colloq. ICALP'92, Vienna, July 1992; Automata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 623, 1992, pp. 186-210]. In particular, we obtain a general method which is useful to show that for several recurrence equations based on the recursive structure of General Probabilistic Divide and Conquer Algorithms, the associated functionals have a unique fixed point which is the solution for the corresponding recurrence equation.     

On a question of Brown, Douglas, and Fillmore

In this note we answer an old question of Brown, Douglas, and Fillmore [L. Brown, R.G. Douglas, P. Fillmore, Unitary equivalence modulo the compact operators and extensions of C^∗-algebras, in: Proc. Conf. Operator Theory, in: Lecture Notes in Math., vol. 345, Springer, Berlin, 1973, pp. 58-128].     

Buchbesprechung

B. Weisfeiler: On Construction and Identification of Graphs. Lecture Notes in Mathematics. Vol. 558. Springer-Verlag, Berlin-Heidelberg-New York 1976, XIV + 237 pp., DM 34,80.

P. Bertsekas: Dynamic Programming and Stochastic Control, Mathematics in Science and Engineering, Vol. 125, Academic Press New York-San Francisco-London 1976, 394 S., $ 22.50.

H. Schoch: Programming in PL/1. 3., bearbeitete Auflage. BSB B.G. Teubner Verlaggesellschaft, Leipzig 1976, 471 S., 24,50 M.     

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints

In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19–28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25–42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.     

First-order Nilpotent minimum logics: first steps

Inspired by the work done by Baaz et al. (Ann Pure Appl Log 147(1–2): 23–47, 2007; Lecture Notes in Computer Science, vol 4790/2007, pp 77–91, 2007) for first-order Gödel logics, we investigate Nilpotent Minimum logic NM. We study decidability and reciprocal inclusion of various sets of first-order tautologies of some subalgebras of the standard Nilpotent Minimum algebra, establishing also a connection between the validity in an NM-chain of certain first-order formulas and its order type. Furthermore, we analyze axiomatizability, undecidability and the monadic fragments.     

An optimal randomized algorithm for d-variate zonoid depth

A randomized linear expected-time algorithm for computing the zonoid depth [R. Dyckerhoff, G. Koshevoy, K. Mosler, Zonoid data depth: Theory and computation, in: A. Prat (Ed.), COMPSTAT 1996—Proceedings in Computational Statistics, Physica-Verlag, Heidelberg, 1996, pp. 235–240; K. Mosler, Multivariate Dispersion, Central Regions and Depth. The Lift Zonoid Approach, Lecture Notes in Statistics, vol. 165, Springer-Verlag, New York, 2002] of a point with respect to a fixed dimensional point set is presented.     

Multi-sequences with Almost Perfect Linear Complexity Profile and Function Fields over Finite Fields

Sequences with almost perfect linear complexity profile defined by Niederreiter (1997, Lecture Notes in Computer Science, Vol. 304, pp. 37–51, Springer-Verlag, Berlin/New York) are quite important for stream ciphers. In this paper, we investigate multi-sequences with almost perfect linear complexity profile and obtain a construction of such multi-sequences by using function fields over finite fields. Some interesting examples from this construction are presented to illustrate our construction.     

An Auslander-type result for Gorenstein-projective modules

An artin algebra A is said to be CM-finite if there are only finitely many, up to isomorphisms, indecomposable finitely generated Gorenstein-projective A-modules. We prove that for a Gorenstein artin algebra, it is CM-finite if and only if every its Gorenstein-projective module is a direct sum of finitely generated Gorenstein-projective modules. This is an analogue of Auslander's theorem on algebras of finite representation type [M. Auslander, A functorial approach to representation theory, in: Representations of Algebras, Workshop Notes of the Third Internat. Conference, in: Lecture Notes in Math., vol. 944, Springer-Verlag, Berlin, 1982, pp. 105-179; M. Auslander, Representation theory of artin algebras II, Comm. Algebra (1974) 269-310].     

A capacity scaling algorithm for M-convex submodular flow

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367.