On the limits of cache-oblivious rational permutations

Permuting a vector is a fundamental primitive which arises in many applications. In particular, rational permutations, which are defined by permutations of the bits of the binary representations of the vector indices, are widely used. Matrix transposition and bit-reversal are notable examples of rational permutations. In this paper we contribute a number of results regarding the execution of these permutations in cache hierarchies, with particular emphasis on the cache-oblivious setting. We first bound from below the work needed to execute a rational permutation with an optimal cache complexity. Then, we develop a cache-oblivious algorithm to perform any rational permutation, which exhibits optimal work and cache complexities under the tall cache assumption. We finally show that for certain families of rational permutations (including matrix transposition and bit reversal) no cache-oblivious algorithm can exhibit optimal cache complexity for all values of the cache parameters. This latter result specializes the one proved by Brodal and Fagerberg for general permutations to the case of rational permutations, and provides further evidence that the tall cache assumption is often necessary to attain cache optimality in the context of cache-oblivious algorithms.     

Routing Permutations on Hypercube Machines with Half-Duplex Links

Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω⁻¹ in 3⌈n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3n steps.     

Random Data Accesses on a Coarse-Grained Parallel Machine I. One-to-One Mappings

This paper describes deterministic communication-efficient algorithms for performing dynamic permutations on a coarse-grained parallel machine. Our analysis shows that the general permutation operation can be completed inCμn/p(+ lower order terms) time and is optimal and scalable providedn⪢p³+p²τ/μ (nis the size of the permutation or the number of elements distributed across thepprocessors, τ is the start-up overhead, and 1/μ is the data transfer rate).Cis a small constant typically between 2 and 3 for write permutations, slightly higher for read permutations. Modifications to exploit locality of access are presented. Special classes of permutations that are optimal for smaller sizes are also described. A companion paper [22] deals with the problem of random data accesses with hot spots.     

Common Intervals of Multiple Permutations

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations.     

Minimizing total weighted completion time with uncertain data: A stability approach

A single-machine scheduling problem is investigated provided that the input data are uncertain: The processing time of a job can take any real value from the given segment. The criterion is to minimize the total weighted completion time for the n jobs. As a solution concept to such a scheduling problem with an uncertain input data, it is reasonable to consider a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. To find an optimal or approximate permutation to be realized, we look for a permutation with the largest stability box being a subset of the stability region. We develop a branch-and-bound algorithm to construct a permutation with the largest volume of a stability box. If several permutations have the same volume of a stability box, we select one of them due to one of two simple heuristics. The efficiency of the constructed permutations (how close they are to a factually optimal permutation) and the efficiency of the developed software (average CPU-time used for an instance) are demonstrated on a wide set of randomly generated instances with 5 ≤ n ≤ 100.     

Optimal Search for Locally Feasible Solutions of a Linear Function on Permutations

Cybernetics and Systems Analysis - We consider the problem of optimal search for locally feasible solutions of a linear function on the permutations where the linear function takes the values from...     

Routing permutations with link-disjoint and node-disjoint paths in a class of self-routable interconnects

We consider efficiently routing permutations in a class of switch-based interconnects. Permutation is an important communication pattern in parallel and distributed computing systems. We present a generic approach to realizing arbitrary permutations in a class of unique-path, self-routable interconnects. It is well-known that this type of interconnect has low hardware cost, but can realize only a small portion of all possible permutations between its inputs and outputs in a single pass. We consider routing arbitrary permutations with link-disjoint paths and node-disjoint paths in such interconnects in a minimum number of passes. In particular, routing with node-disjoint paths has important applications in emerging optical interconnects. We employ and further expand the Latin square technique used in all-to-all personalized exchange algorithms for this class of interconnects for general permutation routing. Our implementation of permutation routing is optimal in terms of the number of passes that messages are transmitted through the network, and it is near-optimal in network transmission time for sufficiently long messages. The possibility of adopting a single-stage interconnect is also discussed.     

From first principles to the Burrows and Wheeler transform and beyond,via combinatorial optimization

We introduce a combinatorial optimization framework that naturally induces a class of optimal word permutations with respect to a suitably defined cost function taking into account various measures of relatedness between words. The Burrows and Wheeler transform (bwt) (cf. [M. Burrows, D. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994]), and its analog for labelled trees (cf. [P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, in: Proc. of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 198–207]), are special cases in the class. We also show that the class of optimal word permutations defined here is identical to the one identified by Ferragina et al. for compression boosting [P. Ferragina, R. Giancarlo, G. Manzini, M. Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM 52 (2005) 688–713]. Therefore, they are all highly compressible. We also provide, by using techniques from Combinatorics on Words, a fast method to compute bwt without using any end-of-string symbol. We also investigate more general classes of optimal word permutations, where relatedness of symbols may be measured by functions more complex than context length. For this general problem we provide an instance that is MAX-SNP hard, and therefore unlikely to be solved or approximated efficiently. The results presented here indicate that a key feature of the Burrows and Wheeler transform seems to be, besides compressibility, the existence of efficient algorithms for its computation and inversion.     

More restrictive Gray codes for some classes of pattern avoiding permutations

In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three positions which is optimal for n odd. Other refinements have been found for permutation sets enumerated by the numbers of Schröder, Pell, even index Fibonacci numbers and the central binomial coefficients. A general efficient generating algorithm is also given.     

A methodology for the design of optimal traffic shapers incommunication networks

The authors consider the problem of optimally regulating the source traffic in a communication network to simultaneously satisfy a finite number of affine burstiness constraints. They prove that an optimal solution is a series connection of correspondingly dimensioned “leaky buckets.” They propose a simple “fork-join” implementation of the optimal solution and study extensions to the problem of optimally shaping the traffic flow to meet a burstiness constraint specified by a concave increasing function. A consequence of their optimality results is that permutations of leaky buckets in a series connection are input-output equivalent     

A comparison of pivot selection techniques for permutation-based indexing

Recently, permutation based indexes have attracted interest in the area of similarity search. The basic idea of permutation based indexes is that data objects are represented as appropriately generated permutations of a set of pivots (or reference objects). Similarity queries are executed by searching for data objects whose permutation representation is similar to that of the query, following the assumption that similar objects are represented by similar permutations of the pivots. In the context of permutation-based indexing, most authors propose to select pivots randomly from the data set, given that traditional pivot selection techniques do not reveal better performance. However, to the best of our knowledge, no rigorous comparison has been performed yet. In this paper we compare five pivot selection techniques on three permutation-based similarity access methods. Among those, we propose a novel technique specifically designed for permutations. Two significant observations emerge from our tests. First, random selection is always outperformed by at least one of the tested techniques. Second, there is no technique that is universally the best for all permutation-based access methods; rather different techniques are optimal for different methods. This indicates that the pivot selection technique should be considered as an integrating and relevant part of any permutation-based access method.     

Exact and approximation algorithms for sorting by reversals,with application to genome rearrangement

Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and areversal takes an arbitrary substring of elements, and reverses their order.For this problem, we develop two algorithms: a greedy approximation algorithm, that finds a solution provably close to optimal inO(n ²) time and0(n) space forn-element permutations, and a branch- and-bound exact algorithm, that finds an optimal solution in0(mL(n, n)) time and0(n ²) space, wherem is the size of the branch- and-bound search tree, andL(n, n) is the time to solve a linear program ofn variables andn constraints. The greedy algorithm is the first to come within a constant factor of the optimum; it guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch- and-bound algorithm are a novel application of maximum-weight matchings, shortest paths, and linear programming.In a series of experiments, we study the performance of an implementation on random permutations, and permutations generated by random reversals. For permutations differing byk random reversals, we find that the average upper bound on reversal distance estimatesk to within one reversal fork<1/2n andn<100. For the difficult case of random permutations, we find that the average difference between the upper and lower bounds is less than three reversals forn<50. Due to the tightness of these bounds, we can solve, to optimality, problems on 30 elements in a few minutes of computer time. This approaches the scale of mitochondrial genomes.This research was supported by a postdoctoral fellowship from the Program in Mathematics and Molecular Biology of the University of California at Berkeley under National Science Foundation Grant DMS-8720208, and by a fellowship from the Centre de recherches mathématiques of the Université de Montréal.This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada, and the Fonds pour la formation de chercheurs et l'aide à la recherche (Québec). The author is a fellow of the Canadian Institute for Advanced Research.     

Optimal Routing of Parentheses on the Hypercube

We consider a new class of routing requests, or partial permutations, for which we give optimal on-line routing algorithms on the hypercube and shuffle-exchange network. For well-formed words of parentheses our algorithm establishes communication between all matching pairs in logarithmic time. It can be applied to the membership problem for certain subclasses of deterministic context-free languages, such as Dyck languages, and to a number of problems dealing with algebraic expressions.     

短块移动排序算法研究

用短块移动操作对一个排列进行排序是一种染色体基因重排技术。怎样才能找出使用短块移动次数最少的排序算法是计算生物学等领域最热门的研究问题之一。给出了短块移动的最优解算法,对近似算法进行了修改。实验验证了最优解算法和近似算法在实际运行过程中都有较好的表现。     

Games with combinatorial constraints

Decision-making criterions are applied to the determination of optimal player’s strategies in combinatory game-type optimization problems in which combinatory constraints that are imposed on the strategies of one player are determined by permutations and nature acts as the second player. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 134–141, July–August 2008.     

An Optimal Systolic Algorithm for Generating Permutations in Lexicographic Order

A systolic algorithm is described for generating all permutations of n elements in lexicographic order. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory, and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O(n!) time solution. This is an improvement over the best previously known techniques in two respects: the algorithm runs on the (arguably) weakest model of parallel computation, and is cost optimal (assuming the time to output the permutations is counted). The algorithm is extended to run adaptively, i.e., when the number of available processors is other than n.     

三元组布尔置换的构造

布尔置换和bent函数在密码学中起着非常重要的作用。在Coulter和Mesnager所提出的三元组布尔置换广义构造方法（该三元组布尔置换可以用来构造bent函数）的基础上，给出了一个等价的构造三元组布尔置换的具体方法。利用此具体方法，提供了一个构造三元组布尔置换的算法。对三个置换之间的依赖关系做了进一步研究，提出了一个三元组置换成立的充要条件，并给出了一个构造三元组布尔置换的新算法。分析了利用三元组布尔置换所得bent函数的性质。     

Optimal batting orders in one-day cricket

This paper concerns the search for optimal or nearly optimal batting orders in one-day cricket. A search is conducted over the space of permutations of batting orders where simulated annealing is used to explore the space. A non-standard aspect of the optimization is that the objective function (which is the mean number of runs per innings) is unavailable and is approximated via simulation. The simulation component generates runs ball by ball during an innings taking into account the state of the match and estimated characteristics of individual batsmen. The methods developed in the paper are applied to the national team of India based on their performance in one-day international cricket matches.     

A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

Functional and topological relations among banyan multistagenetworks of differing switch sizes

Relations among banyan multistage interconnection networks (MINs) of differing switch sizes are studied. If two N×N networks W and W' have switch sizes r and s, respectively, and if r>s, then W realizes a larger number of permutations than W'. Consequently, the two networks can never be equivalent. However, W may realize all the permutations of W', in which case W is said to functionally cover W' in the strict sense. More generally, W is said to functionally cover W' in the wide sense if the terminals of W can be relabeled so that W realizes all the permutations of W'. Functional covering is topologically characterized, and an optimal algorithm to decide strict functional covering is developed