To solve a time-consuming problem using spare computing power of many PCs in homes and offices through the Internet is called desktop grid computing. The spare computing power varies over time because the original use...
详细信息
ISBN:
(纸本)1932415610
To solve a time-consuming problem using spare computing power of many PCs in homes and offices through the Internet is called desktop grid computing. The spare computing power varies over time because the original users utilize their computers for their own purpose. In this paper, we focus on dynamic task scheduling of a parameter sweep application for desktop grid computing. For this problem, several existing algorithms with performance prediction are known. However they are merely heuristic. In contrast, recently we proposed an approximation algorithm, called RR, for the problem. RR has the property that the spare computing power consumed by a schedule generated by RR is almost optimal if the number of tasks is enough large. Also, RR does not use any prediction information on the underlying resources. This paper experimentally evaluates RR and other two related algorithms with consideration to precision of prediction about the spare computing power.
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-...
详细信息
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-item 0-1 knapsack problem to any relative error tolerance epsilon > 0 in the scaled profit space P*/K = O(1/epsilon(1+delta)) with time O(n log(l/s) + 1/epsilon(2+2delta)) and space O(n + 1/epsilon(2+delta)), where P* and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, delta = alpha/(1 + alpha) and alpha = O(log b). This algorithm reduces the exponent of the complexity bound in [5].
This paper presents monitor placement scheme for single node fault detection in optical network. A single fault at a node may generally produce single/many alarms;as a result it becomes very difficult to detect the ex...
详细信息
ISBN:
(纸本)0780392361
This paper presents monitor placement scheme for single node fault detection in optical network. A single fault at a node may generally produce single/many alarms;as a result it becomes very difficult to detect the exact origin of failure. Our two-phased scheme minimizes the placement of the number of monitors to detect the origin of fault in polynomial time. We demonstrate the performance of our scheme on 14-node NSFnet.
In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We st...
详细信息
In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the DSRP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the DARP in a semirandom setting and in the unweighted case.
The problem of scheduling jobs with precedence constraints is a central problem in Scheduling Theory which arises in many industrial and scientific applications. In this paper we present a polynomial time approximatio...
详细信息
ISBN:
(纸本)3540219463
The problem of scheduling jobs with precedence constraints is a central problem in Scheduling Theory which arises in many industrial and scientific applications. In this paper we present a polynomial time approximation scheme for the problem of scheduling jobs with chain precedence constraints on a fixed number of uniformly related machines. Our algorithm works even if we allow "slow" machines to remain idle.
In this paper we present improved combinatorial approximation algorithms for the k-level facility location problem. First, by modifying the path reduction developed in [ A. A. Ageev, Oper. Res. Lett., 30 ( 2002), pp. ...
详细信息
In this paper we present improved combinatorial approximation algorithms for the k-level facility location problem. First, by modifying the path reduction developed in [ A. A. Ageev, Oper. Res. Lett., 30 ( 2002), pp. 327 - 332], we obtain a combinatorial algorithm with a performance factor of 3.27 for any k greater than or equal to 2, thus improving the previous bound of 4.56 achieved by a combinatorial algorithm. Then we develop another combinatorial algorithm that has a better performance guarantee and uses the first algorithm as a subroutine. The latter algorithm can be recursively implemented and achieves a guarantee factor h( k), where h( k) is strictly less than 3.27 for any k and tends to 3.27 as k goes to infinity. The values of h( k) can be easily computed with an arbitrary accuracy: h( 2) approximate to 2.4211, h( 3) approximate to 2.8446, h(4) approximate to 3.0565, h(5) approximate to 3.1678, and so on. Thus, for the cases of k = 2 and k = 3 the second combinatorial algorithm ensures an approximation factor substantially better than 3, which is currently the best approximation ratio for the k-level problem provided by the noncombinatorial algorithm due to Aardal, Chudak, and Shmoys [ Inform. Process. Lett., 72 ( 1999), pp. 161 - 167].
We extend the classic notion of well-separated pair decomposition [ P. B. Callahan and S. R. Kosaraju, J. ACM, 42 ( 1975), pp. 67 - 90] to the unit-disk graph metric: the shortest path distance metric induced by the i...
详细信息
We extend the classic notion of well-separated pair decomposition [ P. B. Callahan and S. R. Kosaraju, J. ACM, 42 ( 1975), pp. 67 - 90] to the unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points in the plane and for any constant c >= 1, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O( n log n) time. We also show that for the unit-ball graph metric in k dimensions where k >= 3, there exists a c-well-separated pair decomposition with O(n(2-2/k)) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.
Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I subset of or equal to X and J subset of or equal to Y with maximum similarity scor...
详细信息
Given two sequences X and Y, the classical dynamic programming solution to the local alignment problem searches for two subsequences I subset of or equal to X and J subset of or equal to Y with maximum similarity score under a given scoring scheme. In several applications, variants of this problem arise with different objectives and with length constraints on the subsequences I and J. This constraint can be explicit, such as requiring \I\ + \J\ greater than or equal to t, or \J\ < T, or may be implicit such as in cyclic sequence comparison, or as in the maximization of length-normalized scores, and driven by practical considerations. We present a survey of approximation algorithms for various alignment problems with constraints, and several new approximation algorithms. These approximations are in two distinct senses: In one the constraints are satisfied but the score computed is within a prescribed tolerance of the optimum instead of the exact optimum. In another, the alignment returned is assured to have at least the Optimum score with respect to the given constraints, but the length constraints are satisfied to within a prescribed tolerance from the required values. The algorithms proposed involve applications of techniques from fractional programming and dynamic programming.
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.
暂无评论