We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadline...
详细信息
We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a 3/2-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems. (C) 2008 Elsevier B.V. All rights reserved.
For parallel machine architecture the Iterated Longest Fragment algorithm was investigated by Stauffer and Hirschberg [Proc. 8th Int. Parallel Process. Symp., 1994, pp. 344-348] for compressing a text with a static di...
详细信息
For parallel machine architecture the Iterated Longest Fragment algorithm was investigated by Stauffer and Hirschberg [Proc. 8th Int. Parallel Process. Symp., 1994, pp. 344-348] for compressing a text with a static dictionary. Later Nagumo, Lu and Watson [Inform. Process. Lett. 59 (1996) 91-96] proved that the algorithm can be implemented in an on-line way for the classical architecture as well. Beside some experimental results the efficiency of the algorithm has not been analyzed yet. In this paper we will investigate the asymptotic worst-case behaviour of the ILF algorithm for several types of static dictionaries. (C) 2001 Elsevier Science B.V. All rights reserved.
Evolutionary algorithms have been successfully applied to various multi-objective optimization problems. However, theoretical studies on multi-objective evolutionary algorithms, especially with self-adaption, are rela...
详细信息
Evolutionary algorithms have been successfully applied to various multi-objective optimization problems. However, theoretical studies on multi-objective evolutionary algorithms, especially with self-adaption, are relatively scarce. This paper analyzes the convergence properties of a self-adaptive (mu + 1)-algorithm. The convergence of the algorithm is defined, and general convergence conditions are studied. Under these conditions, it is proven that the proposed self-adaptive (mu + 1)-algorithm converges in probability or almost surely to the Pareto-optimal front. (c) 2007 Elsevier B.V. All rights reserved.
Binary merge is the best general-purpose merging algorithm known to date. Binary merge consists of two components: a first component in which an array index is incremented by a number nearly equal to the ratio of the ...
详细信息
Binary merge is the best general-purpose merging algorithm known to date. Binary merge consists of two components: a first component in which an array index is incremented by a number nearly equal to the ratio of the sizes of the two arrays being merged followed by a second component, binary search. In this paper we formulate a simple algorithm called interpolation merge, where the binary search component is replaced with linear search, and analyze its expected behavior over data drawn from a uniform distribution. Our results, both theoretical and experimental, indicate a constant factor (almost-equal-to 0.75) speed-up over straight two-way merge. Further, our analysis of interpolation merge, which uses a mechanism of incremental indexing similar to that in binary merge, will hopefully lead to a better understanding of the latter algorithm. Currently, no significant results are known about the expected behavior of binary merge over data drawn from any standard probability distribution.
作者：
Grandi, FabioUniv Bologna
Dept Comp Sci & Engn DISI Alma Mater Studiorum Viale Risorgimento 2 I-40135 Bologna BO Italy
The Bloom filter is a simple random binary data structure which can be efficiently used for approximate set membership testing. When testing for membership of an object, the Bloom filter may give a false positive, who...
详细信息
The Bloom filter is a simple random binary data structure which can be efficiently used for approximate set membership testing. When testing for membership of an object, the Bloom filter may give a false positive, whose probability is the main performance figure of the structure. We complete and extend the analysis of the Bloom filter available in the literature by means of the gamma-transform approach. Known results are confirmed and new results are provided, including the variance of the number of bits set to 1 in the filter. We consider the choice of bits to be set to 1 when an object is inserted both with and without replacement, in what we call standard and classic Bloom filter, respectively. Simple iterative schemes for the computation of the false positive probability and a new non-iterative approximation, taking into account the variance of bits set to 1, are also provided. (C) 2017 Elsevier B.V. All rights reserved.
In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the ex...
详细信息
In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is O(1/rho n(2) log n) for graphs with n nodes and nt edges, where rho is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected O(1/rho n(2) log n) iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if rho = O(n(-1-epsilon)) epsilon > 0. (C) 2007 Elsevier B.V. All fights reserved.
The asymptotic expected storage and access efficiency of recursive bucket methods (N-trees) is examined. Much is known about the expected behavior of N-partitions, even assuming a general distribution of keys. The e...
详细信息
The asymptotic expected storage and access efficiency of recursive bucket methods (N-trees) is examined. Much is known about the expected behavior of N-partitions, even assuming a general distribution of keys. The expected performance of N-trees, however, has only been analyzed for the uniform key distribution. Somewhat better bounds for this case are derived than those presented in previous work. It is shown that for ''smooth'' key distributions with exponentially vanishing tails, the expected storage and search costs are asymptotically less than 4 times those for the uniform distribution. For N-partitions, search cost is not similarly bounded. N-trees are thus an efficient and robust search structure.
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Mod...
详细信息
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Model GB exhibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) as the number of variables approaches infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1)) of the average number of nodes in a search tree used by the backtracking algorithm on Model GB is also presented. It is shown that the average number of nodes required for finding all solutions or proving that no solution exists grows exponentially with the number of variables. So this model might be an interesting distribution for studying the nature of hard instances and evaluating the performance of CSP algorithms. In addition, we further investigate the behaviour of the average number of nodes as r (the ratio of constraints to variables) varies. The results indicate that as r increases, random CSP instances get easier and easier to solve, and the base for the average number of nodes that is exponential in n tends to 1 as r approaches infinity. Therefore, although the average number of nodes used by the backtracking algorithm on random CSP is exponential, many CSP instances will be very easy to solve when r is sufficiently large.
The m-ary method for computing x(E) partitions the bits of the integer E into words of constant length, and then performs as many multiplications as there are nonzero words. Variable length partitioning strategies hav...
详细信息
The m-ary method for computing x(E) partitions the bits of the integer E into words of constant length, and then performs as many multiplications as there are nonzero words. Variable length partitioning strategies have been suggested to reduce the number of nonzero words, and thus, the total number of multiplications. algorithms for exponentiation using such partitioning strategies are termed sliding window techniques. In this paper, we give algorithmic descriptions of two recently proposed sliding window techniques, and calculate the average number of multiplications by modeling the partitioning process as a Markov chain;We tabulate the optimal values of the partitioning parameters, and show that the sliding window algorithms require up to 8% fewer multiplications than the m-ary method.
暂无评论