Finding common RNA pseudoknot structures in polynomial time

This paper presents the first polynomial time algorithm for finding common RNA substructures that include pseudoknots and similar structures. While a more general problem is known to be NP-hard, this algorithm exploits special features of RNA structures to match RNA bonds correctly in polynomial time. Although the theoretical upper bound on the algorithm?s time and space usage is high, the data-driven nature of its computation enables it to avoid computing unnecessary cases, dramatically reducing the actual running time. The algorithm works well in practice, and has been tested on sample RNA structures that include pseudoknots and pseudoknot-like tertiary structures.     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

Efficient lattice assessment for LCG and GLP parameter searches

In the present paper we show how to speed up lattice parameter searches for Monte Carlo and quasi-Monte Carlo node sets. The classical measure for such parameter searches is the spectral test which is based on a calculation of the shortest nonzero vector in a lattice. Instead of the shortest vector we apply an approximation given by the LLL algorithm for lattice basis reduction. We empirically demonstrate the speed-up and the quality loss obtained by the LLL reduction, and we present important applications for parameter selections.

     

Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction

Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for the design of stream ciphers. In this paper, we solve the FCSR synthesis problem for multi-sequences by two rational approximation algorithms using lattice theory. One is based on the lattice reduction greedy algorithm proposed by Nguyen and Stehlé (ACM Trans Algorithms (TALG) 5(4):46, 2009). The other is based on the LLL algorithm which is a polynomial time lattice reduction algorithm. Both of these rational approximation algorithms can find the smallest common FCSR for a given multi-sequence but with different numbers of known terms. When the number of sequences within the multi-sequence is less than or equal to 3, the former is suggested because it has better time complexity and fewer terms are needed. Otherwise, the latter will have better time complexity.     

Lifting and recombination techniques for absolute factorization

In the vein of recent algorithmic advances in polynomial factorization based on lifting and recombination techniques, we present new faster algorithms for computing the absolute factorization of a bivariate polynomial. The running time of our probabilistic algorithm is less than quadratic in the dense size of the polynomial to be factored.     

Multi-Label Markov Random Fields as an Efficient and Effective Tool for Image Segmentation,Total Variations and Regularization

One of the classical optimization models for image segmentation is the well known Markov Random Fields (MRF) model. This model is a discrete optimization problem, which is shown here to formulate many continuous models used in image segmentation. In spite of the presence of MRF in the literature, the dominant perception has been that the model is not effective for image segmentation. We show here that the reason for the non-effectiveness is due to the lack of access to the optimal solution. Instead of solving optimally, heuristics have been engaged. Those heuristic methods cannot guarantee the quality of the solution nor the running time of the algorithm. Worse still, heuristics do not link directly the input functions and parameters to the output thus obscuring what would be ideal choices of parameters and functions which are to be selected by users in each particular application context.We describe here how MRF can model and solve efficiently several known continuous models for image segmentation and describe briefly a very efficient polynomial time algorithm, which is provably fastest possible, to solve optimally the MRF problem. The MRF algorithm is enhanced here compared to the algorithm in Hochbaum (2001) by allowing the set of assigned labels to be any discrete set. Other enhancements include dynamic features that permit adjustments to the input parameters and solves optimally for these changes with minimal computation time. Several new theoretical results on the properties of the algorithm are proved here and are demonstrated for images in the context of medical and biological imaging. An interactive implementation tool for MRF is described, and its performance and flexibility in practice are demonstrated via computational experiments.We conclude that many continuous models common in image segmentation have discrete analogs to various special cases of MRF and as such are solved optimally and efficiently, rather than with the use of continuous techniques, such as PDE methods, which restrict the type of functions used and furthermore, can only guarantee convergence to a local minimum.     

Reducing an arbitrary fullerene to the dodecahedron

Viewing fullerenes as plane graphs with facial cycles being pentagonal and hexagonal only, it is shown how to reduce an arbitrary fullerene to the (graph of the) dodecahedron. This can be achieved by a sequence of eight reduction steps, seven of which are local operations and the remaining reduction step acts globally. In any case, the resulting algorithm has polynomial running time.     

CAD and Topology of Semi-Algebraic Sets

Although Cylindrical Algebraic Decomposition (CAD) is widely used to study the topology of semi-algebraic sets (especially algebraic curves), there are very few studies of the topological properties of the output of the CAD algorithms. In this paper three possible bad topological properties of the output of CAD algorithms are described. It is shown that these properties may not occur after a generic change of coordinates and that they may be avoided, in dimension not greater than three, with a modification of the CAD algorithm. As this modification of the CAD algorithm requires to solve some polynomial systems, it is also shown that the computation with real algebraic numbers may be advantageously replaced, in all the variants of the CAD algorithm, by solving systems of polynomial equations and inequalities.     

Rapid dynamic programming algorithms for RNA secondary structure

Prediction of RNA secondary structure from the linear RNA sequence is an important mathematical problem in molecular biology. Dynamic programming methods are currently the most useful computer technique but are frequently very expensive in running time. In this paper new dynamic programming algorithms are presented which reduce the required computation. The first polynomial time algorithm is given for predicting general secondary structure.     

Exact algorithms for dominating set

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969ⁿ) time and polynomial space algorithm.     

Smoothed analysis of probabilistic roadmaps

The probabilistic roadmap algorithm is a leading heuristic for robot motion planning. It is extremely efficient in practice, yet its worst case convergence time is unbounded as a function of the input's combinatorial complexity. We prove a smoothed polynomial upper bound on the number of samples required to produce an accurate probabilistic roadmap, and thus on the running time of the algorithm, in an environment of simplices. This sheds light on its widespread empirical success.     

Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts

In this paper, we propose to enhance Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations for polynomial programming problems by developing cutting plane strategies using concepts derived from semidefinite programming. Given an RLT relaxation, we impose positive semidefiniteness on suitable dyadic variable-product matrices, and correspondingly derive implied semidefinite cuts. In the case of polynomial programs, there are several possible variants for selecting such particular variable-product matrices on which positive semidefiniteness restrictions can be imposed in order to derive implied valid inequalities. This leads to a new class of cutting planes that we call v-semidefinite cuts. We explore various strategies for generating such cuts, and exhibit their relative effectiveness towards tightening the RLT relaxations and solving the underlying polynomial programming problems in conjunction with an RLT-based branch-and-cut scheme, using a test-bed of problems from the literature as well as randomly generated instances. Our results demonstrate that these cutting planes achieve a significant tightening of the lower bound in contrast with using RLT as a stand-alone approach, thereby enabling a more robust algorithm with an appreciable reduction in the overall computational effort, even in comparison with the commercial software BARON and the polynomial programming problem solver GloptiPoly.     

Efficient offline algorithms for the bicriteria k-server problem and online applications

In this paper we consider the bicriteria version of the well-known k-server problem in which the cost incurred by an algorithm is evaluated simultaneously with respect to two different edge weightings.We show that it is possible to achieve the same competitive ratios of the previously known online algorithms with a dramatic improvement of the running time, i.e., from exponential to polynomial.Such results are obtained by exploiting new polynomial time algorithms able to find offline solutions whose costs differ from the optimal ones only of additive terms independent from the sequence of requests.     

The Local Cut Lemma

The Lovász Local Lemma is a very powerful tool in probabilistic combinatorics, that is often used to prove existence of combinatorial objects satisfying certain constraints. Moser and Tardos (2010) have shown that the LLL gives more than just pure existence results: there is an effective randomized algorithm that can be used to find a desired object. In order to analyze this algorithm, Moser and Tardos developed the so-called entropy compression method. It turned out that one could obtain better combinatorial results by a direct application of the entropy compression method rather than simply appealing to the LLL. The aim of this paper is to provide a generalization of the LLL which implies these new combinatorial results. This generalization, which we call the Local Cut Lemma, concerns a random cut in a directed graph with certain properties. Note that our result has a short probabilistic proof that does not use entropy compression. As a consequence, it not only shows that a certain probability is positive, but also gives an explicit lower bound for this probability. As an illustration, we present a new application (an improved lower bound on the number of edges in color-critical hypergraphs) as well as explain how to use the Local Cut Lemma to derive some of the results obtained previously using the entropy compression method.     

On testing the divisibility of lacunary polynomials by cyclotomic polynomials

An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.

     

The Hardness of Polynomial Equation Solving

Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids unnecessary branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P$ cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications.     

On approximation algorithms for concave mixed-integer quadratic programming

Concave mixed-integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an \(\epsilon \)-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in \(1/\epsilon \), provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless \(\mathcal {P}=\mathcal {NP}\).     

Polynomial identities for the ternary cyclic sum

We simplify the results of Bremner and Hentzel [J. Algebra 231 (2000) 387–405] on polynomial identities of degree 9 in two variables satisfied by the ternary cyclic sum [a, b, c] = abc + bca + cab in every totally associative ternary algebra. We also obtain new identities of degree 9 in three variables which do not follow from the identities in two variables. Our results depend on (i) the LLL algorithm for lattice basis reduction, and (ii) linearization operators in the group algebra of the symmetric group which permit efficient computation of the representation matrices for a non-linear identity. Our computational methods can be applied to polynomial identities for other algebraic structures.     

A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.