Search

A novel predictive measure that predicts which algorithm is best at any given point in time. Always select the predicted best algorithm to run for the next generation.The performance of our method is very competitive if viewed as another novel "individual" algorithm.A very interesting positive synergistic effect is found between algorithms in our method.A novel performance evaluation method that makes a lot of sense when one has an absolute maximum number of function evaluations allowed in your application.Application on a Heating Ventilation and Air Conditioning design problem demonstrates that the method can be used to solve real world problems with constraints and that it performs better than choosing an algorithm randomly. Many good evolutionary algorithms have been proposed in the past. However, frequently, the question arises that given a problem, one is at a loss of which algorithm to choose. In this paper, we propose a novel algorithm portfolio approach to address the above problem for single objective optimization. A portfolio of evolutionary algorithms is first formed. Covariance Matrix Adaptation Evolution Strategy (CMA-ES), History driven Evolutionary Algorithm (HdEA), Particle Swarm Optimization (PSO2011) and Self adaptive Differential Evolution (SaDE) are chosen as component algorithms. Each algorithm runs independently with no information exchange. At any point in time, the algorithm with the best predicted performance is run for one generation, after which the performance is predicted again. The best algorithm runs for the next generation, and the process goes on. In this way, algorithms switch automatically as a function of the computational budget. This novel algorithm is named Multiple Evolutionary Algorithm (MultiEA). The predictor we introduced has the nice property of being parameter-less, and algorithms switch automatically as a function of budget. The following contributions are made: (1) experimental results on 24 benchmark functions show that MultiEA outperforms (i) Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO); (ii) Population-based Algorithm Portfolio (PAP); (iii) a multiple algorithm approach which chooses an algorithm randomly (RandEA); and (iv) a multiple algorithm approach which divides the computational budget evenly and execute all algorithms in parallel (ExhEA). This shows that it outperforms existing portfolio approaches and the predictor is functioning well. (2) Moreover, a neck to neck comparison of MultiEA with CMA-ES, HdEA, PSO2011, and SaDE is also made. Experimental results show that the performance of MultiEA is very competitive. In particular, MultiEA, being a portfolio algorithm, is sometimes even better than all its individual algorithms, and has more robust performance. (3) Furthermore, a positive synergic effect is discovered, namely, MultiEA can sometimes perform better than the sum of its individual EAs. This gives interesting insights into why an algorithm portfolio is a good approach. (4) It is found that MultiEA scales as well as the best algorithm in the portfolio. This suggests that MultiEA scales up nicely, which is a desirable algorithmic feature. (5) Finally, the performance of MultiEA is investigated on a real world problem. It is found that MultiEA can select the most suitable algorithm for the problem and is much better than choosing algorithms randomly.

The maximum flow problem is a type of network optimization problem in the flow graph theory. Many important applications used the maximum flow problem and thus it has been studied by many researchers using different methods. Ford Fulkerson algorithm is the most popular algorithm that used to solve the maximum flow problem, but its complexity is high. In this paper, a parallel Genetic algorithm is applied to find a maximum flow in a weighted directed graph, by finding the objective function value for each augmenting path from the source to the sink simultaneously in the parallel steps in every iteration. The algorithm is implemented using Message Passing Interface (MPI) library, and results are conducted from a real distributed system IMAN1 supercomputer and were compared with a sequential version of Genetic-Maxflow. The simulation results show this parallel algorithm speedup the running time by achieving up to 50% parallel efficiency.

This paper presents a comparison between the performance of Chemical Reaction Optimization algorithm and Genetic algorithm in solving maximum flow problem with the performance of Ford-Fulkerson algorithm in that. The algorithms have been implemented sequentially using JAVA programming language, and executed to find maximum flow problem using different network size. Ford-Fulkerson algorithm which is based on the idea of finding augmenting path is the most popular algorithm used to find maximum flow value but its time complexity is high. The main aim of this study is to determine which algorithm will give results closer to the Ford-Fulkerson results in less time and with the same degree of accuracy. The results showed that both algorithms can solve Max Flow problem with accuracy results close to Ford Fulkerson results, with a better performance achieved when using the genetic algorithm in term of time and accuracy.

This paper presents a simple and efficient near optimal algorithm, named Maximum Adjacent Minimum degree Algorithm (MAMA) for optimization of minimum vertex cover problem. The proposed algorithm at each step add that maximum degree vertex which is adjacent to minimum degree vertex. The computational complexity and optimality comparison are carried with other state of the art algorithms on small benchmark instances as well as on large benchmark instances to check the efficiency of the proposed algorithm. The proposed algorithm outperforms the other well-known algorithm and returns near optimal result in quick time.

A decentralized random algorithm for flow distribution in complex networks is proposed. The aim is to maintain the maximum flow while satisfying the flow limits of the nodes and links in the network. The algorithm is also used for flow redistribution after a failure in (or attack on) a complex network to avoid a cascaded failure while maintaining the maximum flow in the network. The proposed algorithm is based only on the information about the closest neighbours of each node. A mathematically rigorous proof of convergence with probability 1 of the proposed algorithm is provided.

This study presents an algorithm for MaxFlow problem using "Chemical Reaction Optimization algorithm (CRO)". CRO is a recently established meta-heuristics algorithm for optimization, inspired by the nature of chemical reactions. The main concern is to find the best maximum flow value at which the flow can be shipped from the source node to the sink node in a flow network without violating any capacity constraints in which the flow of each edge remains within the upper bound value of the capacity. The proposed MaxFlow-CRO algorithm is presented, analyzed asymptotically and experimental test is conducted. Asymptotic runtime is derived theoretically. The algorithm is implemented using JAVA programming language. Results show a good performance with a complexity of O(I E2), for I iterations and E edges. The number of iterations I in the algorithm, is an important factor that will affect the results obtained. As number of iterations is increased, best possible max-Flow value is obtained.

The flow decomposition algorithm transforms an arc flow-based solution to a network flow problem into flows on directed paths and cycles. When the undirected graph induced by arcs with positive flow is a tree, a circle, or an augmented tree (with n nodes), the standard implementation of the algorithm runs in O (n2) time. In this article, we exploit the structure of the network to develop an O (n) flow decomposition algorithm. The run-time relies on the property that for these networks, paths or cycles can be represented implicitly in O (1) space. The algorithm is easy to implement and does not use complicated data structures. Because the size of the input is O (n), our algorithm is the fastest possible for flow decomposition on these special networks. Our algorithm can be used to improve run-times for solving matching and transportation problems on trees and circles. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.

an algorithm which reduces the arbitrary instance of the network flow problem to a simple path disjoint network in polynomial time. Then the flow in each path is taken as the minimum of the arc capacities of that path from where the flow in each arc can be easily determined. The polynomial time algorithm can determine any instance of the network flow problem faster than the previously existing algorithms . An example has been given to elucidate the process. At the end a MATLAB program based on this algorithm has been given.

The problem of finding maximum flow in network graph is extremely interesting and practically applicable in many fields in our daily life, especially in transportation. Therefore, a lot of researchers have been studying this problem in various methods. Especially in 2013, we has developed a new algorithm namely, postflow-pull algorithm to find the maximum flow on traditional networks. In this paper, we revised postflow-push methods to solve this problem of finding maximum flow on extended mixed network. In addition, to take more advantage of multi-core architecture of the parallel computing system, we build this parallel algorithm. This is a completely new method not being announced in the world. The results of this paper are basically systematized and proven. The idea of this algorithm is using multi processors to work in parallel by postflow_push algorithm. Among these processors, there is one main processor managing data, sending data to the sub processors, receiving data from the sub-processors. The sub-processors simultaneously execute their work and send their data to the main processor until the job is finished, the main processor will show the results of the problem.

Computing flow in a directed graph is a fundamental problem to which other programs can be reduced. The objective associated with the flow networks problem is to maximize the flow through the network. So it is usually studied within the field of Optimization. A parallel approach for obtaining maximum flow in a network is presented here. The concept of layered network is used here. The algorithm proceeds in two passes, forward and backward passes. Each node in a layer are processed in parallel. The time complexity of the algorithm is analyzed to be O(n2logkn).

The ML-EM (maximum likelihood expectation maximization) algorithm is the most popular image reconstruction method when the measurement noise is Poisson distributed. This short paper considers the problem that for a given noisy projection data set, whether the ML-EM algorithm is able to provide an approximate solution that is close to the true solution. It is well-known that the ML-EM algorithm at early iterations converges towards the true solution and then in later iterations diverges away from the true solution. Therefore a potential good approximate solution can only be obtained by early termination. This short paper argues that the ML-EM algorithm is not optimal in providing such an approximate solution. In order to show that the ML-EM algorithm is not optimal, it is only necessary to provide a different algorithm that performs better. An alternative algorithm is suggested in this paper and this alternative algorithm is able to outperform the ML-EM algorithm.

In this paper, we present a novel asynchronous multithreaded algorithm for the maximum network flow problem. The algorithm is based on the classical push-relabel algorithm, which is essentially sequential and requires intensive and costly lock usages to parallelize it. The novelty of the algorithm is in the removal of lock and barrier usages, thereby enabling a much more efficient multithreaded implementation. The newly designed push and relabel operations are executed completely asynchronously and each individual process/thread independently decides when to terminate itself. We further propose an asynchronous global relabeling heuristic to speed up the algorithm. We prove that our algorithm finds a maximum flow with O(|V|2||-E|) operations, where |V| is the number of vertices and |E| is the number of edges in the graph. We also prove the correctness of the relabeling heuristic. Extensive experiments show that our algorithm exhibits better scalability and faster execution speed than the lock-based parallel push-relabel algorithm.

K-Means algorithm is one of the mostly used foundation algorithm in data mining, it base on a greedy clustering algorithm. This paper will introduce this algorithm and analysis. Then prove the correctness of the algorithm. And then show the productivity of this algorithm. And at last, this paper will show some improvement to K-Means algorithm, including how to choose initial center points, and how to calculate the means. This will improve the algorithm at a certain extent.

Preemptive open-shop scheduling problem was studied, and a network flow based algorithm was presented. Firstly, based on the characteristics of the preemptive open-shop, the scheduling problem was formulated as a mixed-integer programming model with the objective to minimize the make-span. The maximum flow model of the preemptive open-shop was developed to model the machine resource allocation and time constraints. Moreover a new preflow push algorithm for the maximum flow model was put forward. Based on the solution of machine resource allocation problem got by preflow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set. Finally, the validity of the developed scheduling algorithm is illustrated by randomly generated example.

This research presents efficient methods for computing the maximum sum in a subarray problem. Firstly, one of the presented methods uses an efficient algorithm that determines the boundaries of a convex shape to calculate the optimal gain. The time complexity of this algorithm is the same as that for other existing algorithms, such as Kadane’s algorithm. Furthermore, even though this algorithm involves complicated operations, the involved processes return the shape of the optimised solution. Secondly, a generalization of the derived efficient algorithm is presented in this paper. This algorithm finds the first maximum sum, second maximum sum and up to the k th maximum sum. Finding the kth maximum convex sum can be utilized in many applications, such as accurately and efficiently locating the spreading of cancer.

This paper presents a new grid-associated algorithm to improve the performance of a D8 algorithm based distributed hydrological model computation. The algorithm is based on the well known single-flow D8 algorithm of grid flow. This algorithm allocates calculation priorities according to the distance between the units and the outlet, then carries out the ergodic computations of the hydrological units according to the priority division. For the parallelized algorithm, a standard thread-level shared memory system for parallel programming (OpenMP-Open specifications for Multi Processing) was introduced, and the parallel coding was implemented in C language. A case study showed that the absolute speed-up ratio of the grid-associated algorithm is 1.64 over the original D8 algorithm, and the linear speed-up ratio of the parallel associated algorithm is 2.42 under 4 cores. The parallel grid-associated algorithm can be applied to a variety of research fields that use the grid method.

The Frank-Wolfe algorithm has been extensively adopted in recent decades to solve the user-equilibrium problem because of its simple structure and low memory requirements. However, Dial observed that the results obtained by the Frank-Wolfe algorithm differed markedly from the B algorithm of Dial in terms of link flows, and the results obtained via Frank-Wolfe algorithm could be incorrect. This study attempts to provide a clear example showing that the Frank-Wolfe algorithm has difficulty in achieving an ϵ-user equilibrium state when ϵ is sufficiently small. An Augmented Frank-Wolfe algorithm is presented that overcomes the weaknesses of the conventional arc-based Frank-Wolfe algorithm.

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.

In this paper, the algorithm of network maximum flow based on network flow matrix is introduced first, then some new properties of network flow matrix are studied according to max-flow min-cut theorem, and on this basis the improved algorithm of network maximum flow based on network flow matrix is given. In this way, the matrix can be reduced order directly when it satisfies certain particular conditions and be translated into several matrices when its order is large, thus simplifying the original algorithm.

The author introduces a minimum cost maximum flows (MCMF) routing algorithm that allows the construction of a multicast tree that incorporates both static and dynamic nodes. The key idea of the algorithm is, first, finding the least delay path of the partial static tree (PST) from a source node to a set of static receivers, by using the ratio of "delay/number of flows" as cost function; and second, adding the dynamic nodes to the constructed PST, one by one, according to their arrival order, by minimizing the ratio "delay/number of flows." According to the presented simulation, this algorithm is superior to shortest path tree (SPT) technique and minimum delay maximum degree algorithm (MDMDA). This result is obtained according to certain simulation parameters and to the tool used to construct the graphs, regarding the total tree cost and the total tree flows criteria, when there is no delay constraint.

Fujishige proposed a polynomial-time maximum flow algorithm using maximum adjacency (MA) orderings. Computational results by Fujishige and Isotani showed that the algorithm was slower in practice than Goldberg and Tarjan's algorithm. In this paper we propose an improved version of Fujishige's algorithm using preflows. Our computational results show that the improved version is much faster than the original one in practice.

The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations.

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.

We study computing maximum flows for real-worldnetworks. In contrast to prior studies, our implementation is bulksynchronous. Our algorithm applies push and relabel operationson all active vertices in parallel, and maintains a preflow througha delayed flow update approach with handshakes between flowpushing and flow receiving.In our implementation the heuristics are no longer entangledwith the push and relabel operations as in prior implementations.We apply two heuristics well known for the sequential algorithm,that is, global relabel and gap relabel, to our parallel implementation.Experiments on networks constructed for computer visionimages show that our parallel implementation on the target 8-core machine is up to 8.6 times faster than the best sequentialimplementation.We aslo propose a new augmenting path based heuristic forsmall-world graphs. On large social networks with up to billionsof edges our implementation achieves close to 40 times parallelspeedup.

In order to raise solving speed of the two-dimensional open dimension optimization algorithm, an improved parallel algorithm based on BSBIS algorithm is proposed, namely p-BSBIS. To overcome the defect of BSBIS algorithm which spends long time for complexity of the algorithm, p-BSBIS can shorten the packing time to a certain extent by using multiple nodes for parallel computing. Furthermore, the improved algorithm not only increases the operation speed but also retains accurate optimization of the original BSBIS. Simulated in the platform, the results demonstrated that p-BSBIS is better than the original algorithm for solving speed.

We present an alternate linear algorithm for finding the minimum flow in (s, t)-planar networks using a new concept of minimal removable sets developed here. The iterative nature of the algorithm facilitates the adjustment of solutions for systems in developmental stages. The minimum flow algorithm presented here requires O(|V|) time, where V denotes the set of vertices. The minimum flow problem arises in many transportation and communication systems.

Query optimization of database management systems is aimed at finding an optimal access path for a query to minimize the evaluation cost. This research addresses the problem of query optimization for databases in which objects frequently change their values. A greedy, adaptive query optimization algorithm is proposed to evaluate relational queries and queries containing complex objects. Rather than constructing a full plan for an access path and executing it, the algorithm constructs a partial plan, executes it, updates the statistics, and constructs a new partial plan. Since a partial plan is constructed based on the latest statistics, the algorithm is adaptive to data modifications and errors from the statistics. It is proved that the algorithm can produce an optimal solution for a class of queries. Furthermore, experiments show that the overhead associated with the algorithm is negligible and the algorithm is efficient for other cases. An adaptive query optimization algorithm for distributed environments is also proposed. The algorithm extends the SDD-1 algorithm to local area networks by considering local processing cost as well as communication cost. Whereas the SDD-1 algorithm only uses semi-joins to reduce communication cost, the algorithm reduces it with joins as well. It is proved that the adaptive algorithm is more efficient than the SDD-1 algorithm.

The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why algorithms behave that way. We have limited our study to the best previous maximum flow algorithms and some of the recent algorithms that are likely to be efficient in practice. Our study encompasses ten maximum flow algorithms and five classes of networks. The augmenting path algorithms tested by us include Dinic's algorithm, the shortest augmenting path algorithm, and the capacity-scaling algorithm. The preflow-push algorithms tested by us include Karzanov's algorithm, three implementations of Goldberg-Tarjan's algorithm, and three versions of Ahuja-Orlin-Tarjan's excess-scaling algorithms. Among many findings, our study concludes that the preflow-push algorithms are substantially faster than other classes of algorithms, and the highest-label preflow-push algorithm is the fastest maximum flow algorithm for which the growth rate in the computational time is O ( n 1.5 ) on four out of five of our problem classes. Further, in contrast to the results of the worst-case analysis of maximum flow algorithms, our study finds that the time to perform relabel operations (or constructing the layered networks) takes at least as much computation time as that taken by augmentations and/or pushes.

Data generated in sensor networks may have different importance and priority. Different types of data contribute differently for scientists to analyze the physical environment. In a challenging environment, wherein sensor nodes do not always have connected paths to the base station, and not all the data can be preserved inside the network due to severe energy constraints and storage constraints at sensor nodes, how to preserve data with maximum priority is a new and challenging problem. In this paper, we study how to preserve data that yield maximum total priorities, under the constraints that each sensor node has limited energy level and storage capacity. We design an efficient optimal algorithm and prove its optimality. The core of the problem is a maximum weighted flow problem, which is to maximize the total weight of flow in the network considering different flows have different weights. Maximum weighted flow is a generalization of the classic maximum flow problem, wherein each unit of flow has the same weight. To the best of our knowledge, our work is the first to study and solve the maximum weighted flow problem. We propose a more time efficient heuristic algorithm. Via simulation, we show that it performs comparably to the optimal algorithm and performs better than the classic maximum flow algorithm, which does not consider data priority. Finally we design a distributed data preservation algorithm based on push-relabel algorithm, analyze its time and message complexities, and empirically show that it outperforms the push-relabel distributed maximum flow algorithm in terms of the total preserved priorities.

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.

Most existing algorithms for parallel or distributed reduction operations are not able to handle temporary or permanent link and node failures. Only recently, methods were proposed which are in principal capable of tolerating link and node failures as well as soft errors like bit flips or message loss. A particularly interesting example is the pushflow algorithm. However, on closer inspection, it turns out that in this method the failure recovery often implies severe performance drawbacks. Existing mechanisms for failure handling may basically lead to a fall-back to an early stage of the computation and consequently slow down convergence or even prevent convergence if failures occur too frequently. Moreover, state-of-the-art fault tolerant distributed reduction algorithms may experience accuracy problems even in failure free systems. We present the push-cancel-flow (PCF) algorithm, a novel algorithmic enhancement of the push-flow algorithm. We show that the new push-cancel-flow algorithm exhibits superior accuracy, performance and fault tolerance over all other existing distributed reduction methods. Moreover, we employ the novel PCF algorithm in the context of a fully distributed QR factorization process and illustrate that the improvements achieved at the reduction level directly translate to higher level matrix operations, such as the considered QR factorization.

Efficient retrieval of replicated data from multiple disks is a challenging problem. Traditional retrieval techniques assume that replication is done at a single site using homogeneous disk arrays having no initial load or network delay. Recently, generalized retrieval algorithms are proposed to cover heterogeneous disk arrays, initial loads, and network delays. Generalized retrieval algorithms achieve the optimal response time retrieval schedule by performing multiple runs of a maximum flow algorithm. Since the maximum flow algorithm is used as a black box technique, flow values of the previous runs cannot be conserved to speed up the process. In this paper, we propose integrated maximum flow algorithms for the generalized optimal response time retrieval problem. Our first algorithm uses Ford-Fulkerson method and the second algorithm uses Push-relabel algorithm. Besides the sequential implementations, a multi-threaded version of the push-relabel algorithm is also implemented. Proposed algorithms are investigated using various replication schemes, query types, query loads, disk specifications, and system delays. Experimental results show that the sequential integrated push-relabel algorithm runs up to 2.5X faster than the black box version. Furthermore, parallel integrated push-relabel implementation achieves up to 1.7X speed up (~1.2X on average) over the sequential algorithm using two threads, which makes the integrated algorithm up to 4.25X (~3X on average) faster than its black box counterpart.

International audience; A minimum cost maximum flow algorithm is proposed for resources (e.g. virtual machines) placement in clouds confronted to dynamic workloads and flows variations. The algorithm is compared to an exact method generalizing the classical Bin-Packing formulation using a linear integer program. A directed graph is used to model the allocation problem for cloud resources organized in a finite number of resource types; a common practice in cloud services. Providers can use the minimum cost maximum flow algorithm to opportunistically select the most appropriate physical resources to serve applications or to ensure elastic platform provisioning. The modified Bin-Packing algorithm is used to benchmark the minimum cost maximum flow solution. The latter combined with a prediction mechanism to handle dynamic variations achieves near optimal performance.

Publisher Summary This chapter presents graphical processing unit (GPU) algorithms for the maximum network flow problem. Maximum network flow is a fundamental graph theory problem with applications in many areas. Compared with data-parallel problems that have been deployed onto GPUs, the maximum network flow problem is more challenging for GPUs owing to intensive data and control dependencies. Two GPU-based maximum flow algorithms are presented in this chapter—the first one is asynchronous and lock free, whereas the second one is synchronized through the precoloring technique. The first algorithm solves the maximum flow problem by using atomic operations to perform the push and relabel operations asynchronously. The second algorithm works on precolored graphs and avoids race condition through barriers. Experiments using the NVIDIA C1060 GPU show that, despite the intrinsic challenges of data dependencies and divergent execution paths, both algorithms are able to achieve at least 3 times, and up to 8 times, speed-ups over implementations on a quad-core Intel Xeon CPU. It also demonstrates algorithm design and implementation, GPUs are also capable of accelerating intrinsically data-dependent problems.

We consider the classical power management problem: There is a device which has two states ON and OFF and one has to develop a control algorithm for changing between these states as to minimize (energy) cost when given a sequence of service requests. Although an optimal 2-competitive algorithm exists, that algorithm does not have good performance in many practical situations, especially in case the device is not used frequently. To take the frequency of device usage into account, we construct an algorithm based on the concept of "slackness degree." Then by relaxing the worst case competitive ratio of our online algorithm to 2+e, where e is an arbitrary small constant, we make the algorithm flexible to slackness. The algorithm thus automatically tunes itself to slackness degree and gives better performance than the optimal 2-competitive algorithm for real world inputs. In addition to worst case competitive ratio analysis, a queueing model analysis is given and computer simulations are reported, confirming that the performance of the algorithm is high.

We study the static load balancing problem in a distributed computer system with the tree hierarchy configuration. It is formulated as a nonlinear optimization problem. After studying the conditions that the solution to the optimization problem of the tree hierarchy network satisfies, we demonstrate that the special structure of the optimization problem leads to an interesting decomposition technique. A new effective decomposition algorithm to solve the optimization problem is presented. The proposed algorithm Is compared with two other well known algorithms: the Flow Deviation (FD) algorithm and the Dafermos-Sparrow (D-S) algorithm. It is shown that the amounts of the storage required for the proposed algorithm and the FD algorithm are O(n) for load balancing of an n-node system. However, the amount of the storage required for the D-S algorithm is O(n log(n)). By using numerical experiments, we show that both the proposed algorithm and the D-S algorithm have much faster convergence in terms of central processing unit (CPU) time than the FD algorithm. >

This paper presents a simple approach to work out maximum flows at minimum cost. The algorithm, on which the algorithm depends, is verified strictly. The algorithm can obtain a lot of adjusting paths in every iteration. An example is given to demonstrate the use of the algorithm. The algorithm has the merits to be programmed easily and of good convergence, and many experiments have verified its great practicability and effectiveness. It can help teaching improvement and practice application. It is also worth popularization.

This paper points out the existing problems in NDRR algorithm, puts forward an improved algorithm and conducts simulation contrast. The result shows the new algorithm can better solve the existing problems of NDRR algorithm.

Fast and efficient protein sequence alignment and comparison algorithms have become significance as the size of databases grow very rapidly. This paper introduces a parallel algorithm for Hashing-N-Gram-Hirschberg (HNGH) algorithm. The HNGH algorithm is an extension of N-Gram-Hirschberg (NGH) algorithm which was proposed by Abdul Rashid in 2007. The parallel algorithm is proposed to speed up the sequential HNGH when run on large database. Our parallel algorithm has two levels of parallelization, one on processors level and the other one on the cores level. By testing our previous work with different Gram lengths ranges from 3–6 letters, HNGH algorithm outperforms the former algorithm (NGH algorithm) in most cases. The parallel algorithm shows an enhancement in the execution time but the speed up is a bit low because of the high communication among processers and the high dependency among the tasks.

The Graphics Processing Unit (GPU) is an asymmetric, heterogeneous multi-core architecture that can be used for high performance parallel computing applications. However, a significant level of interest has been focused on algorithms for solving regular problems, as these applications typically map well to the GPU. Irregular applications, which rely on pointer or graph-based data structures, have not been as extensively studied and are significantly more difficult to implement or map in an efficient fashion on the GPU. In this paper, we consider a graph-based maximum ???ow algorithm that has applications in network optimization problems. In the literature, the push-relabel maximum ???ow algorithm has been considered on the GPU. We believe that Malhotra, Pramodh Kumar and Maheshwari’s algorithm is better suited for the GPU due to the synchronous, iterative nature of the algorithm. As a result, we choose this algorithm for our study. We show that the performance of the GPU algorithm far exceeds that of a sequential CPU algorithm.

The maximum flow problem is one of the classical combinatorial optimization problems. Most of the traditional maximum flow problems are based on "Augmented chain theorem". According to the characteristics of ant system algorithm, we transform the maximum flow problem correspondingly, and then we utilize the ant system algorithm to resolve the problem. In this paper we use ant system algorithm to solve the maximum flow problem, and the simulation results show that the ant system algorithm can be used to resolve the maximum flow problem, and this also provided a new approach to the study on the maximum flow problem.

This paper presents a genetic algorithm to optimize uni-objective problems with an infinite number of optimal solutions. The algorithm uses the maximin concept and e-dominance to promote diversity over the admissible space. The proposed algorithm is tested with two well-known functions. The practical results of the algorithm are in good agreement with the optimal solutions of these functions. Moreover, the proposed optimization method is also applied in two practical real-world engineering optimization problems, namely, in radio frequency circuit design and in kinematic optimization of a parallel robot. In all the cases, the algorithm draws a set of optimal solutions. This means that each problem can be solved in several different ways, all with the same maximum performance.