A parallel extended GCD algorithm

A new parallel extended GCD algorithm is proposed. It matches the best existing parallel integer GCD algorithms of Sorenson and Chor and Goldreich, since it can be achieved in O(n/logn) time using at most n¹⁺ processors on CRCW PRAM. Sorenson and Chor and Goldreich both use a modular approach which consider the least significant bits. By contrast, our algorithm only deals with the leading bits of the integers u and v, with uv. This approach is more suitable for extended GCD algorithms since the coefficients of the extended version a and b, such that au+bv=gcd(u,v), are deeply linked with the order of magnitude of the rational v/u and its continuants. Consequently, the computation of such coefficients is much easier.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm

A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time.     

GCD矩阵的一种推广

本文研究了有限个正整数直积上的GCD矩阵.利用Mbius反演得到了直积上的GCD矩阵性质和GCD矩阵行列式的计算方法.进一步,把正整数直积上的GCD矩阵推广到一般偏序集直积上,得到了广义GCD矩阵的性质.     

New frameworks for Montgomery's modular multiplication method

We present frameworks for fast modular multiplication based on a modification of Montgomery's original method. For (fixed) large integers, our algorithms may be significantly faster than conventional methods. Our techniques may also be extended to modular polynomial arithmetic.

     

On structures of modular adjacency algebras of Johnson schemes

In this paper, we consider algebras over a field of characteristic p, which are generated by adjacency algebras of Johnson schemes. If the algebra is semisimple, the structure is the same as that of the well-known Bose-Mesner algebras. We determine the structure of the algebra when it is not semisimple.     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.     

One-modulus residue arithmetic algorithm to solve linear equations exactly

The paper presents an error-free algorithm to solve linear equations using the residue arithmetic. Simultaneously with solving linear equation system, the exact value of determinant of the system matrix is also calculated. The algorithm removes roundoff errors and according to this kind of errors ensures stability of the solution. It is suitable for implementation for computers with possibility of vector operations.     

A partial enumeration algorithm for pure nonlinear integer programming

In this paper, a partial enumeration algorithm is developed for a class of pure IP problems. Then, a computational algorithm, named PE_SPEEDUP (partial enumeration speedup), has been developed to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many pure IP problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm and the PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

Longest run of equal parts in a random integer composition

This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n$n$. The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196).     

Integer convex minimization by mixed integer linear optimization

Minimizing a convex function over the integral points of a bounded convex set is polynomial in fixed dimension (Grötschel et al., 1988). We provide an alternative, short, and geometrically motivated proof of this result. In particular, we present an oracle-polynomial algorithm based on a mixed integer linear optimization oracle.     

A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the bi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm.     

Computational efficiency analysis of Wu et al.’s fast modular multi-exponentiation algorithm

Very recently, for speeding up the computation of modular multi-exponentiation, Wu et al. presented a fast algorithm combining the complement recoding method and the minimal weight binary signed-digit representation technique. They claimed that the proposed algorithm reduced the number of modular multiplications from 1.503k to 1.306k on average, where the value k is the maximum bit-length of two exponents. However, in this paper, we show that their claim is unwarranted. We analyze the computational efficiency of Wu et al.’s algorithm by modeling it as a Markov chain. Our main result is that Wu et al.’s algorithm requires 1.471k modular multiplications on average.     

Springer basic sets and modular Springer correspondence for classical types

We define the notion of basic set data for finite groups (building on the notion of basic set, but including an order on the irreducible characters as part of the structure), and we prove that the Springer correspondence provides basic set data for Weyl groups. Then we use this to determine explicitly the modular Springer correspondence for classical types (defined over a base field of odd characteristic $p$, and with coefficients in a field of odd characteristic $?\ne p$): the modular case is obtained as a restriction of the ordinary case to a basic set. In order to do so, we compare the order on bipartitions introduced by Dipper and James with the order induced by the Springer correspondence. We provide a quick proof, by sorting characters according to the dimension of the corresponding Springer fibre, an invariant which is directly computable from symbols.     

Existence of a limiting distribution for the binary GCD algorithm

In this article, we prove the existence and uniqueness of a certain distribution function on the unit interval. This distribution appears in Brent's model of the analysis of the binary gcd algorithm. The existence and uniqueness of such a function was conjectured by Richard Brent in his original paper [R.P. Brent, Analysis of the binary Euclidean algorithm, in: J.F. Traub (Ed.), New Directions and Recent Results in Algorithms and Complexity, Academic Press, New York, 1976, pp. 321–355]. Donald Knuth also supposes its existence in [D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, third ed., Addison-Wesley, Reading, MA, 1997] where developments of its properties lead to very good estimates in relation to the algorithm. We settle here the question of existence, giving a basis to these results, and study the relationship between this limiting function and the binary Euclidean operator B₂, proving rigorously that its derivative is a fixed point of B₂.     

A topological approach to divisibility of arithmetical functions and GCD matrices

Considering lower closed sets as closed sets on a preposet (P, ≤), we obtain an Alexandroff topology on P. Then order preserving functions are continuous functions. In this article we investigate order preserving properties (and thus continuity properties) of integer-valued arithmetical functions under the usual divisibility relation of integers and power GCD matrices under the divisibility relation of integer matrices.     

A theorem on integer flows on cartesian products of graphs

It is shown that the Cartesian product of two nontrivial connected graphs admits a nowhere‐zero 4‐flow. If both factors are bipartite, then the product admits a nowhere‐zero 3‐flow. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 93–98, 2003