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.     

Parallel permutation generation on linear array

Given n items, a parallel algorithm for generating all the n! permutations is presented. The computational model used is a linear array which consists of n identical processing elements with a simple structure. One permutation is produced at each other time step. The elapsed time to produce a permutation is independent of the integer n. The basic idea used is the iterative method and the exchange of two consecutive components in an existing permutation. The design procedures of this algorithm are considered in detail. The ranking and unranking functions of the required permutations are also discussed.     

The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework, Parallelization and Experimental Evaluation

We consider triply-nested loops of the type that occur in the standard Gaussian elimination algorithm, which we denote by GEP (or the Gaussian Elimination Paradigm). We present two related cache-oblivious methods I-GEP and C-GEP, both of which reduce the number of cache misses incurred (or I/Os performed) by the computation over that performed by standard GEP by a factor of $\sqrt{M}We consider triply-nested loops of the type that occur in the standard Gaussian elimination algorithm, which we denote by GEP (or the Gaussian Elimination Paradigm). We present two related cache-oblivious methods I-GEP and C-GEP, both of which reduce the number of cache misses incurred (or I/Os performed) by the computation over that performed by standard GEP by a factor of ?M\sqrt{M}, where M is the size of the cache. Cache-oblivious I-GEP computes in-place and solves most of the known applications of GEP including Gaussian elimination and LU-decomposition without pivoting and Floyd-Warshall all-pairs shortest paths. Cache-oblivious C-GEP uses a modest amount of additional space, but is completely general and applies to any code in GEP form. Both I-GEP and C-GEP produce system-independent cache-efficient code, and are potentially applicable to being used by optimizing compilers for loop transformation.     

Sorting by Short Block-Moves

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in the study of genome rearrangements and in the design of interconnection networks. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3 -approximation algorithm for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorithm for this class of permutations is devised that employs graph matching techniques. A linear-time maximum matching algorithm for a special class of grid graphs improves the time complexity of the algorithm for woven double-strip permutations. Received June 1, 1997; revised July 25, 1998.     

An empirical study of cache-oblivious polygon indecomposability testing

We implement and undertake an empirical study of the cache-oblivious variant of the polygon indecomposability testing algorithm of Gao and Lauder, based on a depth-first search (DFS) traversal of the computation tree. According to Abu Salem, the cache-oblivious variant exhibits improved spatial and temporal locality over the original one, and its spatial locality is optimal. Our implementation revolves around eight different variants of the DFS-based algorithm, tailored to assess the trade-offs between computation and memory performance as originally proposed by Abu Salem. We analyse performance sensitively to manipulations of the several parameters comprising the input size. We describe how to construct suitably random families of input that solicit such variations, and how to handle redundancies in vector computations at no asymptotic increase in the work and cache complexities. We report extensively on our experimental results. In all eight variants, the DFS-based variant achieves excellent performance in terms of L1 and L2 cache misses as well as total run time, when compared to the original variant of Gao and Lauder. We also benchmark the DFS variant against the powerful computer algebra system MAGMA, in the context of bivariate polynomial irreducibility testing using polygons. For sufficiently high degree polynomials, MAGMA either runs out of memory or fails to terminate after about 4 h of execution. In contrast, the DFS-based version processes such input using a couple of seconds. Particularly, we report on absolute irreducibility testing of bivariate polynomials of total degree reaching 19,000 in about 2 s for the DFS variant, using a single processor.     

Sorting Unsigned Permutations by Weighted Reversals,Transpositions, and Transreversals

Reversals, transpositions and transreversals are common events in genome rearrangement. The genome rearrangement sorting problem is to transform one genome into another using the minimum number of given rearrangement operations. An integer permutation is used to represent a genome in many cases. It can be divided into disjoint strips with each strip denoting a block of consecutive integers. A singleton is a strip of one integer. And the genome rearrangement problem turns into the problem of sorting a permutation into the identity permutation equivalently. Hannenhalli and Pevzner designed a polynomial time algorithm for the unsigned reversal sorting problem on those permutations with O(log n) singletons. In this paper, first we describe one case in which Hannenhalli and Pevzner’s algorithm may fail and propose a corrected approach. In addition, we propose a (1+ε)-approximation algorithm for sorting unsigned permutations with O(log n) singletons by reversals of weight 1 and transpositions/transreversals of weight 2.     

Optimizing graph algorithms for improved cache performance

We develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of /spl Omega/(N/sup 3///spl radic/C), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.     

Hot-potato algorithms for permutation routing

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2ⁿ hypercube: O(n²) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2ⁿ-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2ⁿ) steps     

三元组布尔置换的构造

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

一种面向自动向量化和数据置换操作的中间表示

在现有的SIMD程序设计中,编译器或程序员都需要借助置换指令对参与运算的向量操作数进行重新组织,才能符合SIMD指令的要求。这些置换指令带来了较大的性能损失。本文提出了一种新的中间表示,它能够完整地记录标量和向量操作数的存储地址信息,使得置换指令的产生尽可能地推后,减少了冗余置换指令的产生。利用这种中间表示实现了一种数据置换操作的优化算法,它能够有效地减少置换指令带来的性能损失。面向一组典型的多媒体程序进行测试的结果表明,本文提出的方法可以平均获得7%的性能加速。     

置换表示方法求解多卫星多地面站调度问题

针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.     

More on permutation generation methods

We study a class of recursive permutation generation methods which construct a sequence of alln! permutations ofn elements by repeatedly generating all permutations of the elements in the firstn?1 positions and exchanging one of them with the element in then-th position. We give a general principle which enables us to obtain a whole class of permutation generation methods. This class includes the well-known algorithms of Wells and Heap as special cases, but contains also many new simple algorithms. Moreover, we are able to produce permutation generation methods with prescribed properties concerning the change that should be made in order to skip a block ofm! permutations with fixed elements in positionsm+1, …,n. For any method in our class, this change is a single transposition for any oddm>1, and a cyclic shift along a cycle of lengthm for any evenm.     

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.     

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.     

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.     

通过改变开关状态实现多源点多播

在并行和分布式环境中 ,多个结点之间的通讯一直是研究工作的焦点问题 ,这些通讯主要包括置换、多播(Multicast)及多源点多播 (Multiple Multicast) .L ai提出了适用于一类与带缓存的 Cube网相互拓扑等价的网络的置换算法 ,硬件代价为 O(N log N ) ,算法的时间复杂度为 O(N ) .Feng提出的 inside- out算法实现了 Omega- 1 × Omega网上的置换 ,总的路由时间复杂度为 O(N log N) ,硬件代价为 O(N log N) .支持严格无阻塞置换的三级 Clos网的总的交叉点数为O(N32 ) .支持严格无阻塞的多播的三级 Clos网为 O(N32 logrloglogr) .Yang提出了一种新的多播网络 ,硬件复杂度为 O(N log2 N ) .为了支持多源点多播 ,多级互联网硬件代价往往大幅上升 .本文借鉴了 L ai提出的规则改变开关状态的方法 ,并把这种算法推广到了多源点多播的情况 .提出了一种新的多源点多播路由算法 ,此算法也同样适用于这一类相互拓扑等价的多级互联网 ,包括 Baseline、Om ega、Cube等 .在此算法中 ,每个数据流被划分为固定大小的数据包 ,在网络中独立传送 ,网络中的每个开关的状态按照固定的状态每个时步规则变化 ,每个数据包两次经过网络后到达目标结点 .此类的网络的硬件代价为 O(Nlog N ) ,此多源点多播路由算法的时间复杂度为 O(N )     

A new approximation algorithm for sorting of signed permutations

Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions.Namely,given any two permutations,find the shortest distance between them.This problem is related with genome rearrangement,genes are oriented in DNA sequences.The transpositions which have been studied in the liteature can be viewed as operations working on two consecutive segments of the genome.In this paper,a new kind of transposition which can work on two arbitrary segments of the genome is proposed,and the sorting of signed permutations by reversals and this new kind of transpostitions are studied.After establishing a lower bound on the number of operations needed,a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.     

Construction of Hamiltonian paths in graphs of permutation polyhedra

The problem of finding an extremum of a linear function over a permutation set is considered. The polyhedron of admissible values of this function over permutations is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path in the graph corresponding to the permutation set for n=4.     

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.     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).