Finding the automorphism group of a circulant association scheme in polynomial time

A polynomial-time algorithm for finding the automorphism group of a circulant association scheme is constructed. The correctness of the algorithm is based on a new result generalizing the Burnside-Schur theorem (on permutation groups having a regular cyclic subgroup) in the class of automorphism groups of association schemes. Bibliography: 14 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 321, 2005, pp. 251–267.     

Efficient representation of perm groups

This note presents an elementary version of Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate lowlevel data structures. Upper and lower bounds on the running time are also obtained. (Following a suggestion of Vaughan Pratt, we adopt the convention that perm=permutation, perhaps thereby saving millions of syllables in future research.)Dedicated to the memory of Marshall HallThis research was supported in part by the National Science Foundation under grant CCR-86-10181, and by Office of Naval Research contract N00014-87-K-0502.     

An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs

In this paper we present an optimal algorithm to solve the all-pairs shortest path problem on permutation graphs with n vertices and m edges which runs in O(n ²) time. Using this algorithm, the average distance of a permutation graph can also be computed in O(n ²) time.     

A spectral algorithm for envelope reduction of sparse matrices

The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope-reducing reordering is obtained by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. This Laplacian eigenvector solves a continuous relaxation of a discrete problem related to envelope minimization called the minimum 2-sum problem. The permutation vector computed by the spectral algorithm is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reording algorithm usually computes smaller envelope sizes than those obtained from the current standards such as the Gibbs—Poole—Stockmeyer (GPS) algorithm or the reverse Cuthill—McKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.     

Permutation binomials and their groups

This paper is devoted to studying the properties of permutation binomials over finite fields and the possibility to use permutation binomials as encryption functions. We present an algorithm for enumeration of permutation binomials. Using this algorithm, all permutation binomials for finite fields up to order 15000 were generated. Using this data, we investigate the groups generated by the permutation binomials and discover that over some finite fields \mathbb F_q {{\mathbb F}_q} , every bijective function on [1..q − 1] can be represented as a composition of binomials. We study the problem of generating permutation binomials over large prime fields. We also prove that a generalization of RSA using permutation binomials is not secure. Bibliography: 9 titles.     

求置换因子循环矩阵的逆阵及广义逆阵的快速算法

1 引 言 循环矩阵由于其应用非常广泛而成为一类重要的特殊矩阵,如在图象处理、编码理论、自回归滤波器设计等领域中经常会遇到以这类矩阵为系数的线性系统的求解问题.而对称循环组合系统也具有广泛的实际背景,例如造纸机的横向控制系统,具有平行结     

全错位排列问题的基于芯片的DNA计算模型

全错位排列问题作为组合数学中一个重要的问题,到目前为止还没有好的算法.应用DNA芯片技术,提出了全错位排列问题的基于芯片的DNA计算模型,并对模型进行了简要分析.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

A new algorithm for generating derangements

A new algorithm for generating derangements based on a well known permutation generation method is presented and analysed. The algorithm is shown to be superior in storage and time requirements to the existing method.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC-A3336.     

On generation of permutations through decomposition of symmetric groups into cosets

A hardware-oriented algorithm for generating permutations is presented that takes as a theoretic base an iterative decomposition of the symmetric groupS _n into cosets. It generates permutations in a new order. Simple ranking and unranking algorithms are given. The construction of a permutation generator is proposed which contains a cellular permutation network as a main component. The application of the permutation generator for solving a class of combinatorial problems on parallel computers is suggested.     

How to find small AI-systems for antiblocking decoding

The antiblocking decoding algorithm established in Kroll and Vincenti (2010) [6] is based on the notion of an antiblocking system. It is comparable with the permutation decoding algorithm. Instead of a permutation decoding set, called a PD-set, consisting of automorphisms of the code, it uses an antiblocking system, called an AI-system, consisting of information sets.As the permutation decoding algorithm is more efficient the smaller the PD-set, so the antiblocking decoding algorithm is more effective the smaller the AI-system. Therefore, it is important for the applications to find small AI-systems.As in the case of PD-sets, there is no method that guarantees in general how to construct optimal or nearly optimal AI-systems.In this paper, we present first some general results on the existence and construction of small antiblocking systems using properties of antiblocking systems derived in Kroll and Vincenti (2008) [4]. The crucial point for the construction of antiblocking systems is a lemma, in which a recursive procedure is provided. In the second part, we apply these findings to construct small AI-systems for some codes arising from a cap of 20 points in PG(4,3).     

Antiblocking decoding

Based on the notion of an antiblocking system a new decoding algorithm is developed which is comparable with the permutation decoding algorithm, but more efficient.     

A simplified loop-free algorithm for generating permutations

A simple loop-free algorithm for generation of all permutations of a set of elements is presented and its validity is proved. It is a simplification of Ehrlich's loop-free version of Johnson and Trotter's algorithm. Each permutation is generated by exchanging two adjacent elements of the preceding permutation. A very simple data structure obviates the need for looping during the generation of each successive permutation.     

A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion

In this paper, we present a discrete artificial bee colony algorithm to solve the no-idle permutation flowshop scheduling problem with the total tardiness criterion. The no-idle permutation flowshop problem is a variant of the well-known permutation flowshop scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions: First of all, a discrete artificial bee colony algorithm is presented to solve the problem on hand first time in the literature. Secondly, some novel methods of calculating the total tardiness from makespan are introduced for the no-idle permutation flowshop scheduling problem. Finally, the main contribution of the paper is due to the fact that a novel speed-up method for the insertion neighborhood is developed for the total tardiness criterion. The performance of the discrete artificial bee colony algorithm is evaluated against a traditional genetic algorithm. The computational results show its highly competitive performance when compared to the genetic algorithm. Ultimately, we provide the best known solutions for the total tardiness criterion with different due date tightness levels for the first time in the literature for the Taillard’s benchmark suit.     

Polynomial time recognition and testing of isomorphism of cyclic tournaments

By a tournament is meant an oriented graph any pair of whose vertices is joined by precisely one directed edge; a tournament is cyclic if its automorphism group contains a permutation whose cyclic decomposition consists of a unique cycle containing all vertices. In the present paper we describe an algorithm for recognizing the isomorphism of cyclic tournaments. This algorithm has an arbitrary tournament as input. For this tournament, in polynomial time in the number of its vertices it determines its cyclicity, and when it is cyclic it constructs a canonical form for the tournament and generators of its automorphism group. A procedure which constructs the set of all nonconjugate Hamiltonian permutations for a given permutation group of odd order in polynomial time is of independent interest. The technique of construction of the basic algorithm uses both classical results of the theory of computational complexity with permutation groups and Schur's method of S-rings.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklovaa AN SSSR, Vol. 192, pp. 74–111, 1991.     

Circular permutation graph family with applications

In a circular permutation diagram, there are two sets of terminals on two concentric circles: C_in and C_out. Given a permutation Π = [π₁, π₂, …, π_n], terminal i on C_in and terminal π_i on C_out are connected by a wire. The intersection graph G_c of a circular permutation diagram D_c is called a circular permutation graph of a permutation Π corresponding to the diagram D_c. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δV_clog logV_c,V_clogV_c) + E_c) time algorithm for finding a maximum independent set of a circular permutation diagram D_c, where δ is the minimum degree of vertices in the intersection graph G_c = (V_c,E_c) of D_c. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

Exact Stratified Linear Rank Tests for Ordered Categorical and Binary Data

Abstract

We present an efficient algorithm for generating exact permutational distributions for linear rank statistics defined on stratified 2 × c contingency tables. The algorithm can compute exact p values and confidence intervals for a rich class of nonparametric problems. These include exact p values for stratified two-population Wilcoxon, Logrank, and Van der Waerden tests, exact p values for stratified tests of trend across several binomial populations, exact p values for stratified permutation tests with arbitrary scores, and exact confidence intervals for odds ratios embedded in stratified 2 × c tables. The algorithm uses network-based recursions to generate stratum-specific distributions and then combines them into an overall permutation distribution by convolution. Where only the tail area of a permutation distribution is desired, additional efficiency gains are achieved by backward induction and branch-and-bound processing of the network. The algorithm is especially efficient for highly imbalanced categorical data, a situation where the asymptotic theory is unreliable. The backward induction component of the algorithm can also be used to evaluate the conditional maximum likelihood, and its higher order derivatives, for the logistic regression model with grouped data. We illustrate the techniques with an analysis of two data sets: The leukemia data on survivors of the Hiroshima atomic bomb and data from an animal toxicology experiment provided by the U.S. Food and Drug Administration.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.