Designing bijective S-boxes using Algorithm Portfolios with limited time budgets

Substitution boxes (S-boxes) are essential parts of symmetric-key cryptosystems. Designing S-boxes with satisfactory nonlinearity and autocorrelation properties is a challenging task for both theoretical algebraic methods and computational optimization algorithms. Algorithm Portfolios (APs) are algorithmic schemes where multiple copies of the same algorithm or different algorithms share the available computational resources, running concurrently or interchangeably on a number of processors. Recently, APs have gained increasing attention due to their remarkable efficiency in multidisciplinary applications. The present work is a preliminary study of parallel APs on the bijective S-boxes design problem. The proposed APs comprise two state-of-the-art heuristic algorithms, namely Simulated Annealing and Tabu Search, and they are parallelized according to the master-slave model without exchange of information among the constituent algorithms. The proposed APs are experimentally assessed on typical problem instances under limited time budgets. Different aspects of their performance is analyzed, suggesting that the considered APs are competitive in terms of solution quality and running time against their constituent algorithms as well as different approaches.     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

A learning approach to the bandwidth multicolouring problem

In this article, a generalisation of the vertex colouring problem known as bandwidth multicolouring problem (BMCP), in which a set of colours is assigned to each vertex such that the difference between the colours, assigned to each vertex and its neighbours, is by no means less than a predefined threshold, is considered. It is shown that the proposed method can be applied to solve the bandwidth colouring problem (BCP) as well. BMCP is known to be NP-hard in graph theory, and so a large number of approximation solutions, as well as exact algorithms, have been proposed to solve it. In this article, two learning automata-based approximation algorithms are proposed for estimating a near-optimal solution to the BMCP. We show, for the first proposed algorithm, that by choosing a proper learning rate, the algorithm finds the optimal solution with a probability close enough to unity. Moreover, we compute the worst-case time complexity of the first algorithm for finding a 1/(1–?) optimal solution to the given problem. The main advantage of this method is that a trade-off between the running time of algorithm and the colour set size (colouring optimality) can be made, by a proper choice of the learning rate also. Finally, it is shown that the running time of the proposed algorithm is independent of the graph size, and so it is a scalable algorithm for large graphs. The second proposed algorithm is compared with some well-known colouring algorithms and the results show the efficiency of the proposed algorithm in terms of the colour set size and running time of algorithm.     

A tabu search algorithm based on new block properties and speed-up method for permutation flow-shop with finite intermediate storage

This paper deals with a permutation flow-shop scheduling problem with finite intermediate storage (PFSFIS) between successive machines so as to minimize makespan. In such a problem the intermediate storage capacity constraints are considered besides the machine-related constraints usually discussed in the general permutation flow-shop. This feature adds extra difficulties to the scheduling problem. In this paper, we present some new block properties and a speed-up method using a forward-backward hybrid algorithm to compute makespan. Applied in a tabu search algorithm, the new block properties greatly reduce the neighborhood size and thus shorten the search time. Also, the speed-up method eliminates redundant computation for the objective function and reduces a majority of the running time. Computational experiments (up to 200 jobs and 20 machines) are given to demonstrate the effectiveness of new block neighborhood characteristics and the speed-up method. Compared with the results yielded by the best-known algorithm, the objective function is improved by 0.14% if the new block neighborhood characteristics are used; furthermore, the running time is reduced by 53.7% on the average if the speed-up method is used. Under the condition that both of the algorithms have the same running time the objective function is improved by 0.24% if both of the two above improvement methods are applied in the original tabu search.     

Algorithms for Pre-Compiling Programs by Parallel Compilers

The paper addresses the challenge of transmitting a big number of files stored in a data center (DC), encrypting them by compilers, and sending them through a network at an acceptable time. Face to the big number of files, only one compiler may not be sufficient to encrypt data in an acceptable time. In this paper, we consider the problem of several compilers and the objective is to find an algorithm that can give an efficient schedule for the given files to be compiled by the compilers. The main objective of the work is to minimize the gap in the total size of assigned files between compilers. This minimization ensures the fair distribution of files to different compilers. This problem is considered to be a very hard problem. This paper presents two research axes. The first axis is related to architecture. We propose a novel pre-compiler architecture in this context. The second axis is algorithmic development. We develop six algorithms to solve the problem, in this context. These algorithms are based on the dispatching rules method, decomposition method, and an iterative approach. These algorithms give approximate solutions for the studied problem. An experimental result is implemented to show the performance of algorithms. Several indicators are used to measure the performance of the proposed algorithms. In addition, five classes are proposed to test the algorithms with a total of 2350 instances. A comparison between the proposed algorithms is presented in different tables discussed to show the performance of each algorithm. The result showed that the best algorithm is the Iterative-mixed Smallest-Longest- Heuristic (ISL) with a percentage equal to 97.7% and an average running time equal to 0.148 s. All other algorithms did not exceed 22% as a percentage. The best algorithm excluding ISL is Iterative-mixed Longest-Smallest Heuristic (ILS) with a percentage equal to 21,4% and an average running time equal to 0.150 s.     

关于漂移分析的注记

进化算法成功应用于求解各种复杂优化问题,其理论研究尚处于初级阶段。时间复杂性分析可以估计算法的平均运行时间,是进化算法理论研究中的重要方向和有力工具。讨论了漂移分析和进化算法时间复杂性的关系,利用吸收马尔科夫链给出漂移定理的一个新的证明;用一步平均漂移估计算法计算时间,得到了线性函数进化算法时间复杂度的一个一般性的结果。这些结果有助于更好地理解进化算法的工作原理和性能。     

Improved Approximation Bounds for Planar Point Pattern Matching

We analyze the performance of simple algorithms for matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance between the sets. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We introduce a modification to their algorithm, which is based on aligning midpoints rather than endpoints. This modification has the same simplicity and running time as theirs, and we show that it achieves a better approximation ratio of roughly 3.14. We also analyze the approximation ratio in terms of a instance-specific parameter that is based on the ratio between diameter of the pattern set to the optimum Hausdorff distance. We show that as this ratio increases (as is common in practical applications) the approximation ratio approaches 3 in the limit. We also investigate the performance of the algorithm by Goodrich et al. as a function of this ratio, and present nearly matching lower bounds on the approximation ratios of both algorithms. This work was supported by the National Science Foundation under grants CCR-0098151 and CCF-0635099.     

Benchmarking and Comparison of the Task Graph Scheduling Algorithms

The problem of scheduling a parallel program represented by a weighted directed acyclic graph (DAG) to a set of homogeneous processors for minimizing the completion time of the program has been extensively studied. The NP-completeness of the problem has stimulated researchers to propose a myriad of heuristic algorithms. While most of these algorithms are reported to be efficient, it is not clear how they compare against each other. A meaningful performance evaluation and comparison of these algorithms is a complex task and it must take into account a number of issues. First, most scheduling algorithms are based upon diverse assumptions, making the performance comparison rather meaningless. Second, there does not exist a standard set of benchmarks to examine these algorithms. Third, most algorithms are evaluated using small problem sizes, and, therefore, their scalability is unknown. In this paper, we first provide a taxonomy for classifying various algorithms into distinct categories according to their assumptions and functionalities. We then propose a set of benchmarks that are based on diverse structures and are not biased toward a particular scheduling technique. We have implemented 15 scheduling algorithms and compared them on a common platform by using the proposed benchmarks, as well as by varying important problem parameters. We interpret the results based upon the design philosophies and principles behind these algorithms, drawing inferences why some algorithms perform better than others. We also propose a performance measure called scheduling scalability (SS) that captures the collective effectiveness of a scheduling algorithm in terms of its solution quality, the number of processors used, and the running time.     

From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time

We propose and study the Maximum Constrained Agreement Subtree (MCAST) problem, which is a variant of the classical Maximum Agreement Subtree (MAST) problem. Our problem allows users to apply their domain knowledge to control the construction of the agreement subtrees in order to get better results. We show that the MCAST problem can be reduced to the MAST problem in linear time and thus we have algorithms for MCAST with running times matching the fastest known algorithms for MAST. A preliminary version of this paper appears in the Proceedings of the Fifth Workshop on Algorithms in Bioinformatics (WABI 2005). Research of H.F. Ting is supported in part by Hong Kong RGC Grant HKU-7172/06E.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

Optimal scheduling of compute-intensive tasks on a network ofworkstations

In a network of high performance workstations, many workstations are underutilized by their owners. The problem of using these idle cycles for solving computationally intensive tasks by executing a large task on many workstations has been addressed before and algorithms with O(N²) time and O(N) space for choosing the optimal subset of workstations out of N workstations were presented. We improve these algorithms to reduce the running time to O(N log N), while keeping the space requirement the same. The proposed algorithms are particularly useful for SPMD parallelism where computation is the same for all workstations and the data space is partitioned between the workstations     

Fully dynamic algorithms for permutation graph coloring

We introduce a dynamic model for maintaining permutation graph coloring. Our motivation comes from the strait type river routing problem in VLSI. This paper presents fully dynamic algorithms for the permutation graph coloring problem. These algorithms are designed to handle Insert and Delete operations and answer some queries. The aim is to provide for running times that are asymptotically more efficient than recomputation (off-line algorithms that run in 0(n logw) time, are known [5,6,10,3]). First, the algorithm A^ that runs in 0(n) uniform running time per Insert/Delete operation is presented. Second, a more sophisticated data structure leads to the algorithm A2 that runs in (9(m logw) uniform running time per Insert I Delete, where m denotes the number of chains in the decomposition. It follows from [7,4] that the running time of A2 when the points from the dynamically changing set are drawn independently from a uniform distribution on the unit square is G(yfn logn) per Insert/Delete in probability. Third, we sketch a composite algorithm A3 that switches between A± and A2 guarantees an amortized running time of (min{n,m logw)) per Insert/Delete. Finally, we outline a number of applications     

A randomized parallel branch-and-bound algorithm

Randomized algorithms are algorithms that employ randomness in their solution method. We show that the performance of randomized algorithms is less affected by factors that prevent most parallel deterministic algorithms from attaining their theoretical speedup bounds. A major reason is that the mapping of randomized algorithms onto multiprocessors involves very little scheduling or communication overhead. Furthermore, reliability is enhanced because the failure of a single processor leads only to degradation, not failure, of the algorithm. We present results of an extensive simulation done on a multiprocessor simulator, running a randomized branch-and-bound algorithm. The particular case we consider is the knapsack problem, due to its ease of formulation. We observe the largest speedups in precisely those problems that take large amounts of time to solve. This work has been supported by the U.S. Army Research Office under Contract No. DAAG 29-85-K-0236.     

Exact bounds on running ASCEND/DESCEND and FAN-IN algorithms onsynchronous multiple bus networks

We consider the problem of running ASCEND/DESCEND and FAN-IN algorithms on synchronous multiple bus networks with a restricted number of buses. Exact lower bounds on the time are derived. We present a method that runs FAN-IN algorithms optimally and ASCEND/DESCEND algorithms in one step beyond the lower bound     

Combinatorial compression algorithms for ordered record sequences

The problem of efficient use and storage of data in memory is considered. Three compression algorithms for ordered sequences of records are proposed, which are essentially faster than the statistical algorithms. The running time of the proposed algorithms is linear in the number of records.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 121–128, November–December, 1991.     

Time-optimal control for discrete-time hybrid automata

In this paper, the problem of time-optimal control for hybrid systems with discrete-time dynamics is considered. The hybrid controller steers all trajectories starting from a maximal set to a given target set in minimum time. We derive an algorithm that computes this maximal winning set. Also, algorithms for the computation of level sets associated with the value function rather than the value function itself are presented. We show that by solving the reachability problem for the discrete time hybrid automata we obtain the time optimal solution as well. The control synthesis is subject to hard constraints on both control inputs and states. For linear discrete-time dynamics, linear programming and quantifier elimination techniques are employed for the backward reachability analysis. Emphasis is given on the computation of operators for non-convex sets using an extended convex hull approach. A two-tank example is considered in order to demonstrate the techniques of the paper.     

基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W[2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。     

Energy and transition-aware runtime task scheduling for multicore processors

Many embedded or portable devices have large demands on running real-time applications. The designers start to adopt the multicore processors in these devices. The multi-core processors, however, cause much higher power consumption than ever before. To resolve this problem, many researchers have focused their studies on designing the energy-aware task scheduling algorithms for multicore processors. Conventional scheduling algorithms assumed that each core can operate under different voltage levels. However, they have not considered the effects of voltage transition overheads, which may defeat the benefit of task scheduling. In this paper, we aim to resolve this scheduling problem with voltage transition overhead consideration. We formalize this problem by an integer linear programming model and propose a heuristic algorithm for a runtime environment. The experimental results show that the proposed online heuristic algorithm can obtain the comparable results with the optimal scheduling derived by the offline integer linear programming approach.     

Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers

This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.     

On-Line Approximate String Searching Algorithms: Survey and Experimental Results

The problem of approximate string searching comprises two classes of problems: string searching with k mismatches and string searching with k differences. In this paper we present a short survey and experimental results for well known sequential approximate string searching algorithms. We consider algorithms based on different approaches including dynamic programming, deterministic finite automata, filtering, counting and bit parallelism. We compare these algorithms in terms of running time against pattern length and for several values of k for four different kinds of text: binary alphabet, alphabet of size 8, English alphabet and DNA alphabet. Finally, we compare the experimental results of the algorithms with their theoretical complexities.