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.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors.     

Finding minimal enclosing boxes

The problem of finding minimal volume boxes circumscribing a given set of three-dimensional points is investigated. It is shown that it is not necessary for a minimum volume box to have any sides flush with a face of the convex hull of the set of points, which makes a naive search problematic. Nevertheless, it is proven that at least two adjacent box sides are flush with edges of the hull, and this characterization enables anO(n ³) algorithm to find all minimal boxes for a set ofn points.     

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.     

A Study of Permutation Networks: New Designs and Some Generalizations

Permutation networks have been used in the literature to model interprocessor and processor-memory interconnections in parallel computers. This paper introduces new permutation network designs and generalizes the notion of a permutation network to provide a more flexible model of such interconnections. The new designs are based concentrators and superconcentrators, and for n inputs they can be optimized to obtain self-routing permutation networks with O(n lg n) cost, O(lg n) depth, and O(lg²n) routing time. The main feature of these new network designs is that they do not require complex routing schemes such as Clos networks since they are inherently self-routing. Generalizations of these designs are also given to obtain permutation networks in which the numbers of inputs and outputs may be different, and/or the maximum number of parallel routes between inputs and outputs can be less than the number of inputs or outputs, or both. For n inputs, αn outputs, and O(n^ϵ) parallel routes, where 0 < α ≤ 1, 0 < ϵ < 1, these generalized designs can be optimized to have permutation networks with O(n) cost, O(lg n), depth, and O(lg²n) routing time. It is shown that the previously known designs, such as Clos networks, result in inferior realizations when compared with these new designs.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

Time-slot assignment for TDMA-systems

In satellite communication as in other technical systems using the TDMA-technique (time division multiple access) the problem arises to decompose a given (n×n)-matrix in a weighted sum of permutation matrices such that the sum of the weights becomes minimal. We show at first that an optimal solution of this problem can be obtained inO(n ⁴)-time using at mostO(n ²) different permutation matrices. Thereafter we discuss shortly the decomposition inO(n) different matrices which turns out to be NP-hard. Moreover it is shown that an optimal decomposition using a class of 2n permutation matrices which are fixed in advance can be obtained by solving a classical assignment problem. This latter problem can be generalized by taking arbitrary Boolean matrices. The corresponding decomposition problem can be transformed to a special max flow min cost network flow problem, and is thus soluble by a genuinely polynomial algorithm.     

Coupled-task scheduling on a single machine subject to a fixed-job-sequence

This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n²) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem.     

Whole mirror duplication-random loss model and pattern avoiding permutations

In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p of duplications of the identity is the class of permutations avoiding the alternating permutations of length p²+1. We also compute the number of duplications necessary and sufficient to obtain any permutation of length n. We provide two efficient algorithms to reconstitute a possible scenario of whole mirror duplications from identity to any permutation of length n. One of them uses the well-known binary reflected Gray code (Gray, 1953) [10]. Other relative models are also considered.     

Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons

We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a temperature parameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. We show that there is an input permutation that causes Spin-the-bottle sort to require Ω(n ²logn) expected time in order to succeed, and that in O(n ²logn) time this algorithm succeeds with high probability for any input. We also show there is a specification of Annealing sort that runs in O(nlogn) time and succeeds with very high probability.     

On the complexity of signed and minus total domination in graphs

In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n²) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.     

Efficient algorithmic learning of the structure of permutation groups by examples

This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G ≤ S_n as input. We discuss randomized algorithms for learning the concepts of group membership, inclusion, and equality by representing the group in terms of its strong sequence of generators using random examples from G. We present O(n³ log n) time sequential learning algorithms for testing membership, inclusion and equality. The running time is expressed as a function of the size of the object set. (G ≤ S_n can have as many as n! elements.) Our bounds hold for all input groups. We also introduce limited parallelism, and our lower processor bounds make our algorithms more practical.Finally, we show that learning two-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over GF(2). We present an O(log³ n) time learning algorithm using n^ω processors for learning two-groups from examples (where n × n matrix product takes logarithmic time using n^ω processors).     

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.     

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.     

A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times,due-window and job rejection

We focus on a due-date assignment model where due-dates are determined by penalties for jobs exceeding pre-specified (job-dependent, different) deadlines. The underlying assumption of this model, denoted by DIF, is that there are "lead times that customers consider to be reasonable and expected". In a minmax DIF model, the value of the objective function is that of the largest job/due-date cost. The goal is to find both the job sequence and the due-dates, such that this value is minimized.In this paper we study several extensions of the minmax DIF model. First, we consider general position-dependent job processing times. Then we extend the model to a setting of a due-window for acceptable lead-times. Here, the assumption is that a time interval exists, such that due-dates assigned to be within this interval are not penalized. The last extension of the DIF model is to a setting allowing job-rejection. This option reflects many real-life situations, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. The first two extensions are shown to be polynomially solvable: we introduce solution algorithms requiring O(n³) and O(n⁴) time, respectively, where n is the number of jobs. The last extension (assuming job-rejection) is proved to be NP-hard in the ordinary sense, and an efficient pseudo-polynomial dynamic programming algorithm is introduced.     

Dominating set based exact algorithms for 3-coloring

We show that the 3-colorability problem can be solved in O(n^1.296) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in ²o(n) time for graphs having minimum degree at least ω(n) where ω(n) is any function which goes to ∞. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a ²o(n) time nor a ²o(m) time algorithm is possible (m denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(n^1.2535) time.     

Simple extractors via constructions of cryptographic pseudo-random generators

Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that do not use designs or polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately in O(log²n) time. These extractors work for weak sources with min-entropy λn, for arbitrary constant λ>0, have seed length O(log²n), and their output length is ≈n^λ/3.     

Optimal routing algorithms for mesh-connected processor arrays

We show that there is a randomizedoblivious algorithm for routing any (partial) permutation on ann ×n grid in 2n +O(logn) parallel communication steps. The queues will not grow larger than Θ(logn/log logn) with high probability. We then modify this to obtain a (nonoblivious) algorithm with the same running time such that the size of the queues is bounded by a constant with high probability. For permutations withlocality, where each packet has to travel a distance at mostL, a generalization of the algorithm routes in time proportional toL with high probability. Finally, we identify a class of meshlike networks that have optimal or near-optimal diameter. These meshes have the potential of being adapted to run existing sorting and routing algorithms with corresponding reduction in their running times.