In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji co...
详细信息
In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.
We consider discrete-time homogeneous systems under arbitrary switching and study their growth rate, the analogue of joint spectral radius for switched linear systems. We show that a system is asymptotically stable if...
详细信息
We consider discrete-time homogeneous systems under arbitrary switching and study their growth rate, the analogue of joint spectral radius for switched linear systems. We show that a system is asymptotically stable if and only if its growth rate is less than unity. We also provide an approximation algorithm to compute growth rate to an arbitrary accuracy.
This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVC...
详细信息
This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.
A multipoint request is a group of collaborating nodes that wish to establish a communication for a certain duration of time. This need arises in parallel applications executed on processing elements connected either ...
详细信息
A multipoint request is a group of collaborating nodes that wish to establish a communication for a certain duration of time. This need arises in parallel applications executed on processing elements connected either by specialized interconnection networks or over wide area networks (collective communication operations). Each individual request is satisfied by a given subtree connecting the participating nodes. We aim to maximize the number of requests that can be simultaneously satisfied. In this paper, we show that this problem is NP-complete and we propose for it an approximation algorithm provided that the number of requests using the same edge is bounded by a constant.
This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA co...
详细信息
This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA constructs the vertex cover by repeatedly adding, at each step, all vertices adjacent to the vertex of minimal degree; in the case of a tie, it selects the one having the maximum sum of degrees of its neighbors. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any other available vertex cover algorithms.
In this paper, a cooperative localization algorithm for autonomous underwater vehicles (AUVs) is proposed. A “parallel” model is adopted to describe the cooperative localization problem instead of the traditional “...
详细信息
In this paper, a cooperative localization algorithm for autonomous underwater vehicles (AUVs) is proposed. A “parallel” model is adopted to describe the cooperative localization problem instead of the traditional “leader-follower” model, and a linear programming associated with convex optimization method is used to deal with the problem. After an unknown-but-bounded model for sensor noise is assumed, bearing and range measurements can be modeled as linear constraints on the configuration space of the AUVs. Merging these constraints induces a convex polyhedron representing the set of all configurations consistent with the sensor measurements. Estimates for the uncertainty in the position of a single AUV or the relative positions of two or more nodes can then be obtained by projecting this polyhedron onto appropriate subspaces of the configuration space. Two different optimization algorithms are given to recover the uncertainty region according to the number of the AUVs. Simulation results are presented for a typical localization example of the AUV formation. The results show that our positioning method offers a good localization accuracy, although a small number of low-cost sensors are needed for each vehicle, and this validates that it is an economical and practical positioning approach compared with the traditional approach.
A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY problem is presented. This algorithm runs in O( log 2 (n + |F|)) parallel time on a CREW PRAM machine using O(n + |F|) processors, where n is the...
详细信息
A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY problem is presented. This algorithm runs in O( log 2 (n + |F|)) parallel time on a CREW PRAM machine using O(n + |F|) processors, where n is the number of variables and |F| is the number of clauses. Performance guarantees are considered for three slightly differing definitions of this problem.
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to...
详细信息
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any n≧8
traveling salesman problem
approximation algorithm
-optimal
minimal spanning tree
triangle inequality
We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of ...
详细信息
We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the vertices have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected. (C) 2012 Elsevier B. V. All rights reserved.
In this paper, we consider a problem of VLSI (very large scale integrated) design occurring in the routing phase. The problem is to determine the optimal size selection for the gates in a combinatorial circuit which u...
详细信息
In this paper, we consider a problem of VLSI (very large scale integrated) design occurring in the routing phase. The problem is to determine the optimal size selection for the gates in a combinatorial circuit which uses the problem of finding a shortest path in an oriented acyclic graph for making certain updates between any two successive iterations. For this NP-hard problem, we give an approximation algorithm.
暂无评论