QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosi...
详细信息
QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosing pivot elements. In order to obtain the result we present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort. We show that for every input the expected number of comparisons is at most for the in-place variant. If we allow n extra bits, then we can lower the bound to . Thus, spending n extra bits we can save more that 0.96n comparisons if n is large enough. Both estimates improve the previously known results. Moreover, our non-in-place variant does essentially use the same number of comparisons as index based Heapsort variants and Relaxed-Weak-Heapsort which use comparisons in the worst case. However, index based Heapsort variants and Relaxed-Weak-Heapsort require extra bits whereas we need n bits only. Our theoretical results are upper bounds and valid for every input. Our computer experiments show that the gap between our bounds and the actual values on random inputs is small. Moreover, the computer experiments establish QuickHeapsort as competitive with Quicksort in terms of running time.
We give a survey of a number of simple applications of renewal theory to problems on random strings and tries: insertion depth, size, insertion mode and imbalance of tries;variations for b-tries and Patricia tries;Kho...
详细信息
We give a survey of a number of simple applications of renewal theory to problems on random strings and tries: insertion depth, size, insertion mode and imbalance of tries;variations for b-tries and Patricia tries;Khodak and Tunstall codes. (C) 2011 Elsevier B.V. All rights reserved.
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard probl...
详细信息
In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard problems are rare. This paper contributes a theoretical understanding of EAs on the NP-hard multiprocessor scheduling problem. The worst-case bound on the (1+1)EA for the multiprocessor scheduling problem and a worst-case example are presented. It is proved that the (1+1)EA on problem achieves an approximation ratio of in expected time . Finally, the theoretical analysis on three selected instances of the multiprocessor scheduling problem shows that EAs outperform local search algorithms on these instances.
We give a unified probabilistic analysis for a general class of bin packing problems by directly analyzing corresponding mathematical programs. In this general class of packing problems, objects are described by a giv...
详细信息
We give a unified probabilistic analysis for a general class of bin packing problems by directly analyzing corresponding mathematical programs. In this general class of packing problems, objects are described by a given number of attribute values. (Some attributes may be discrete;others may be continuous.) Bins are sets of objects, and the collection of feasible bins is merely required to satisfy some general consistency properties. We characterize the asymptotic optimal value as the value of an easily specified linear program whose size is independent of the number of objects to be packed. or as the limit of a sequence of such linear program values. We also provide bounds for the rate of convergence of the average cost to its asymptotic value. The analysis suggests an (a.s.) asymptotically E-optimal heuristic that runs in linear time. The heuristics can be designed to he asymptotically optimal while still running in polynomial time. We also show that in several important cases, the algorithm has both polynomially fast convergence and polynomial running time. This heuristic consists of solving a linear program and rounding its solution up to the nearest integer vector. We show how our results can be used to analyze a general vehicle routing model with capacity and time window constraints.
In this paper, a formal convergence analysis of the conventional PSO algorithms with time-varying parameters is presented. Based on this analysis, a new convergence-related parametric model for the conventional PSO is...
详细信息
In this paper, a formal convergence analysis of the conventional PSO algorithms with time-varying parameters is presented. Based on this analysis, a new convergence-related parametric model for the conventional PSO is introduced. Finally, several new schemes for parameter adjustment, providing significant performance benefits, are introduced. Performance of these schemes is empirically compared to conventional PSO algorithms on a set of selected benchmarks. The tests prove effectiveness of the newly introduced schemes, especially regarding their ability to efficiently explore the search space. (C) 2009 Elsevier B.V. All rights reserved.
We analyze a simple greedy algorithm for finding small dominating sets in undirected graphs of N nodes and M edges. We show that d(g) less-than-or-equal-to N + 1 - square-root 2 M + 1, where d(g) is the cardinality of...
详细信息
We analyze a simple greedy algorithm for finding small dominating sets in undirected graphs of N nodes and M edges. We show that d(g) less-than-or-equal-to N + 1 - square-root 2 M + 1, where d(g) is the cardinality of the dominating set returned by the algorithm.
J.M. Kurtzberg proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km × km assignment problem is decomposed into k 2...
详细信息
J.M. Kurtzberg proposed a method of obtaining approximate solutions to the assignment problem by decomposing a large problem into many smaller subproblems. Thus a km × km assignment problem is decomposed into k 2 problems of size m × m and one problem of size k × k . In this paper we analyze the performance of this heuristic, obtaining the following main results: 1. (1) For the maximization problem, the ratio of the optimal solution to the heuristic solution can be as large as, but cannot exceed min( k , m ); 2. (2) For the minimization problem, if k = o( n /log n ) where n = mk , and the matrix elements are independently drawn from a uniform distribution on (0, 1), in the limit the expected value of the heuristic solution is at least k /3 times that of the optimal solution.
Given a set of n elements each of which is either red or blue, Boyer and Moore's MJRTY algorithm uses pairwise equal/not equal color comparisons to determine the majority color. We analyze the average behavior of ...
详细信息
Given a set of n elements each of which is either red or blue, Boyer and Moore's MJRTY algorithm uses pairwise equal/not equal color comparisons to determine the majority color. We analyze the average behavior of their algorithm, proving that if all 2(n) possible inputs are equally likely, the average number of color comparisons used is n - root 2n/pi + O(1) with variance (pi - 2)n/pi - root 2n/pi + O(1). (C) 2013 Elsevier B.V. All rights reserved.
A generalization of the particle swarm optimization (PSO) algorithm is presented in this paper. The novel optimizer, the Generalized PSO (GPSO), is inspired by linear control theory. It enables direct control over the...
详细信息
A generalization of the particle swarm optimization (PSO) algorithm is presented in this paper. The novel optimizer, the Generalized PSO (GPSO), is inspired by linear control theory. It enables direct control over the key aspects of particle dynamics during the optimization process. A detailed theoretical and empirical analysis is presented, and parameter-tuning schemes are proposed. GPSO is compared to the classical PSO and genetic algorithm (GA) on a set of benchmark problems. The results clearly demonstrate the effectiveness of the proposed algorithm. Finally, an application of the GPSO algorithm to the fine-tuning of the support vector machines classifier for electrical machines fault detection is presented. (C) 2011 Elsevier Inc. All rights reserved.
An algorithm for the scheduling of events in a discrete-event simulation system, due to J. O. Henriksen, is presented. An O(n<span class="mn" id="MathJax-Span-11" style="font-size: 7
暂无评论