Orienting rewrite rules with the Knuth–Bendix order

We consider two decision problems related to the Knuth–Bendix order (KBO). The first problem is orientability: given a system of rewrite rules R, does there exist an instance of KBO which orients every ground instance of every rewrite rule in R. The second problem is whether a given instance of KBO orients every ground instance of a given rewrite rule. This problem can also be reformulated as the problem of solving a single ordering constraint for the KBO. We prove that both problems can be solved in the time polynomial in the size of the input. The polynomial-time algorithm for orientability builds upon an algorithm for solving systems of homogeneous linear inequalities over integers. We show that the orientability problem is P-complete. The polynomial-time algorithm for solving a single ordering constraint does not need to solve systems of linear inequalities and can be run in time O(n²). Also we show that if a system is orientable using a real-valued instance of KBO, then it is also orientable using an integer-valued instance of KBO. Therefore, all our results hold both for the integer-valued and the real-valued KBO.     

On the complexity of computing the diameter of a polytope

We show that it isD ^P -hard to determine the combinatorial diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question.     

Integer programming with 2-variable equations and 1-variable inequalities

We present an efficient algorithm to find an optimal integer solution of a given system of 2-variable equalities and 1-variable inequalities with respect to a given linear objective function. Our algorithm has worst-case running time in O(N²) where N is the number of bits in the input.     

Propagating systems of dense linear integer constraints

In interval propagation approaches to solving nonlinear constraints over reals it is common to build stronger propagators from systems of linear equations. This, as far as we are aware, is not pursued for integer finite domain propagation. In this paper we show how we use interval Gauss–Jordan elimination to build stronger propagators for an integer propagation solver. In a similar fashion we present an interval Fourier elimination preconditioning technique to generate redundant linear constraints from a system of linear inequalities. We show how to convert the resulting interval propagators into integer propagators. This allows us to use existing integer solvers. We give experiments that show how these preconditioning techniques can improve propagation performance on dense systems.     

Parallel Approximation Algorithms by Positive Linear Programming

Several sequential approximation algorithms for combinatorial optimization problems are based on the following paradigm: solve a linear or semidefinite programming relaxation, then use randomized rounding to convert fractional solutions of the relaxation into integer solutions for the original combinatorial problem. We demonstrate that such a paradigm can also yield parallel approximation algorithms by showing how to convert certain linear programming relaxations into essentially equivalent positive linear programming [LN] relaxations that can be near-optimally solved in NC. Building on this technique, and finding some new linear programming relaxations, we develop improved parallel approximation algorithms for Max Sat, Max Directed Cut, and Max k CSP. The Max Sat algorithm essentially matches the best approximation obtainable with sequential algorithms and has a fast sequential version. The Max k CSP algorithm improves even over previous sequential algorithms. We also show a connection between probabilistic proof checking and a restricted version of Max k CSP. This implies that our approximation algorithm for Max k CSP can be used to prove inclusion in P for certain PCP classes. Received November 1996; revised March 1997.     

Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

Abstract. We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm greedy-dual-size previously considered in [4] and [5] is (k+1)/(k-h+1) competitive against the optimal strategy with cache size h≤ k . Our proof provides further insights to greedy-dual-size. We also indicate how the same integer programming formulation has been recently used [1], [2] to obtain approximation algorithms to the NP-complete ``offline' problem.     

Solving sparse linear systems of equations using the modified digraph approach

We propose two different algorithms which depend on the modified digraph approach for solving a sparse system of linear equations. The main feature of the algorithms is that the solution of a sparse system of linear equations can be expressed exactly if all the non-zero entries, including the right-hand side, are integers and if none of the products exceeds the size of the largest integer that can be represented in the arithmetic of the computer used. The implementation of the algorithms is tested on five problems. The results are compared with those obtained using an algorithm proposed earlier. It is shown that the efficiency with which a sparse system of linear equations can be analysed by a digital computer using the proposed modified digraph approach as a tool depends mainly on the efficiency with which semifactors and k-semifactors are generated. Finally, in our implementation of the proposed algorithms, the input sparse matrix is stored using a row-ordered list of a modified uncompressed storage scheme.     

Pattern‐Based Quadrangulation for N‐Sided Patches

We propose an algorithm to quadrangulate an N‐sided patch (2 ≤ N ≤ 6) with prescribed numbers of edge subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We demonstrate the effectiveness of our algorithm by integrating it into a sketch‐based quad remeshing system. A reference C++ implementation of our algorithm is provided as a supplementary material.     

Convex inner approximations of nonconvex semialgebraic sets applied to fixed-order controller design

We describe an elementary algorithm to build convex inner approximations of nonconvex sets. Both input and output sets are basic semialgebraic sets given as lists of defining multivariate polynomials. Even though no optimality guarantees can be given (e.g. in terms of volume maximisation for bounded sets), the algorithm is designed to preserve convex boundaries as much as possible, while removing regions with concave boundaries. In particular, the algorithm leaves invariant a given convex set. The algorithm is based on Gloptipoly 3, a public-domain Matlab package solving nonconvex polynomial optimisation problems with the help of convex semidefinite programming (optimisation over linear matrix inequalities, or LMIs). We illustrate how the algorithm can be used to design fixed-order controllers for linear systems, following a polynomial approach.     

Hilbert's tenth problem is of unification type zero

We show that the problem of finding integer solutions to a polynomial equation over the integers has unification type zero, i.e. there exist polynomial equations which have unifiers, but which have no minimal and complete set of unifiers: In particular, it is shown that the equation uv=w+z has no minimal and complete set of solutions.     

A note on solving linear Diophantine systems by using L 3-reduction algorithm

The main difficulty in solving linear Diophantine systems is the very rapid growth of intermediate results which makes many algorithms, for solving linear Diophantine systems, impractical even for large computers. One way for controlling this growth is to use the L ³-reduction algorithm, introduced by Lenstra et al. [A.K. Lenstra, H.W. Lenstra, and L. Lov?sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 515–534.]. Esmaeili [H. Esmaeili, How can we solve a linear Diophantine equation by the basis reduction algorithm, Int. J. Comput. Math. 82 (2005), pp. 1227–1234.] proposed a method for obtaining the general integer solution of a linear Diophantine equation by using L ³-reduction algorithm. Here we propose a procedure for generalizing Esmaeili's method, to a method for obtaining the general integer solution of systems of linear Diophantine equations by using L ³-reduction algorithm. Then we consider the complexity issues and show that the generalized algorithm controls the growth of the intermediate results and the number of required arithmetic operations well. Finally, some illustrative numerical examples are given to show the efficiency of the proposed algorithm.     

A simple proof of the validity of the reduced prs algorithm

Given two univariate polynomials with integer coefficients, it has beenrediscovered [2] that the reduced polynomial remainder sequence (prs) algorithm can be used mainly to compute over the integers the members of anormal prs, keeping under control the coefficient growth and avoiding greatest common divisor (ged) computations of the coefficients. The validity proof of this algorithm as presented in the current literature [2] is very involved and has obscured simple divisibility properties. In this note, we present Sylvester's theorem of 1853 [4] which makes these simple divisibility properties clear for normal prs's. The proof presented here is a modification of Sylvester's original proof.     

Polyhedral studies for minimum-span graph labelling with integer distance constraints

This paper studies the polytope of the minimum‐span graph labelling problems with integer distance constraints (DC‐MSGL). We first introduce a few classes of new valid inequalities for the DC‐MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch‐and‐cut algorithm for solving the DC‐MSGL. Following that, we present our polyhedral results on the dimension of the DC‐MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC‐MSGL on triangular graphs.     

Discrete logarithms inGF(p)

Several related algorithms are presented for computing logarithms in fieldsGF(p),p a prime. Heuristic arguments predict a running time of exp((1+o(1)) ) for the initial precomputation phase that is needed for eachp, and much shorter running times for computing individual logarithms once the precomputation is done. The running time of the precomputation is roughly the same as that of the fastest known algorithms for factoring integers of size aboutp. The algorithms use the well known basic scheme of obtaining linear equations for logarithms of small primes and then solving them to obtain a database to be used for the computation of individual logarithms. The novel ingredients are new ways of obtaining linear equations and new methods of solving these linear equations by adaptations of sparse matrix methods from numerical analysis to the case of finite rings. While some of the new logarithm algorithms are adaptations of known integer factorization algorithms, others are new and can be adapted to yield integer factorization algorithms.     

A Multi-Objective Integer Melody Search Algorithm

There are a number of algorithms for the solution of continuous optimization problems. However, many practical design optimization problems use integer design variables instead of continuous. These types of problems cannot be handled by using continuous design variables-based algorithms. In this paper, we present a multi-objective integer melody search optimization algorithm (MO-IMS) for solving multi-objective integer optimization problems, which take design variables as integers. The proposed algorithm is a modified version of single-objective melody search (MS) algorithm, which is an innovative optimization algorithm, inspired by basic concepts applied in harmony search (HS) algorithm. Results show that MO-IMS has better performance in solving multi-objective integer problems than the existing multi-objective integer harmony search algorithm (MO-IHS). Performance of proposed algorithm is evaluated by using various performance metrics on test functions. The simulation results show that the proposed MO-IMS can be a better technique for solving multi-objective problems having integer decision variables.     

On parallel integer sorting

We present an optimal algorithm for sortingn integers in the range [1,n ^c ] (for any constantc) for the EREW PRAM model where the word length isn , for any >0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.Supported by NSF-DCR-85-03251 and ONR contract N00014-87-K-0310     

On the linear complexity of bounded integer sequences over different moduli

We give a relation between the linear complexity over the integers and over the residue rings modulo m of a bounded integer sequence. This relation can be used to obtain a variety of new results for several sequences widely studied in the literature. In particular we apply it to Sidelnikov sequences.     

A Robust Algorithm for Solving Nonlinear Programming Problems

In this paper, we introduce a new algorithm for solving nonlinear programming (NLP) problems. It is an extension of Guo's algorithm [1] which possesses enhanced capabilities for solving NLP problems. These capabilities include: a) extending the variable subspace, b) adding a search process over subspaces and normalized constraints, c) using an adaptive penalty function, and d) adding the ability to deal with integer NLP problems, 0-1 NLP problems, and mixed-integer NLP problems which have equality constraints. These four enhancements increase the capabilities of the algorithm to solve nonlinear programming problems in a more robust and universal way. This paper will present results of numerical experiments which show that the new algorithm is not only more robust and universal than its competitors, but also its performance level is higher than any others in the literature.     

A Fast and Simple Algorithm for the Money Changing Problem

The Money Changing Problem (MCP) can be stated as follows: Given k positive integers \(a_1< \cdots < a_k\) and a query integer M, is there a linear combination \(\sum_i c_ia_i = M\) with non-negative integers c_i, a decomposition of M? If so, produce one or all such decompositions. The largest integer without such a decomposition is called the Frobenius number g(a₁,...,a_k). A data structure called the residue table of a₁ words can be used to compute the Frobenius number in time O(a₁). We present an intriguingly simple algorithm for computing the residue table which runs in time O(ka₁), with no additional memory requirements, outperforming the best previously known algorithm. Simulations show that it performs well even on "hard" instances from the literature. In addition, we can employ the residue table to answer MCP decision instances in constant time, and a slight modification of size O(a₁) to compute one decomposition for a query M. Note that since both computing the Frobenius number and MCP (decision) are NP-hard, one cannot expect to find an algorithm that is polynomial in the size of the input, i.e., in k,log a_k, and log M. We then give an algorithm which, using a modification of the residue table, also constructible in O(ka₁) time, computes all decompositions of a query integer M. Its worst-case running time is O(ka₁) for each decomposition, thus the total runtime depends only on the output size and is independent of the size of query M itself. We apply our latter algorithm to interpreting mass spectrometry (MS) peaks: Due to its high speed and accuracy, MS is now the method of choice in protein identification. Interpreting individual peaks is one of the recurring subproblems in analyzing MS data; the task is to identify sample molecules whose mass the peak possibly represents. This can be stated as an MCP instance, with the masses of the individual amino acids as the k integers a₁,..., a_k. Our simulations show that our algorithm is fast on real data and is well suited for generating candidates for peak interpretation.     

A nonconforming finite element method for a singularly perturbed boundary value problem

We analyze a new nonconforming Petrov-Galerkin finite element method for solving linear singularly perturbed two-point boundary value problems without turning points. The method is shown to be convergent, uniformly in the perturbation parameter, of orderh ^1/2 in a norm slightly stronger than the energy norm. Our proof uses a new abstract convergence theorem for Petrov-Galerkin finite element methods.