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.
The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have ...
详细信息
The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1 + 1) evolutionary algorithm (EA). A runtime bound of order O(m log m), where m is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(m log(1 /epsilon)) until reaching an expected relative solution quality of 1 - epsilon, and a runtime of O(m log m) until reaching the optimal solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1 + 1) EA on OneMax for a proper ACO algorithm. (c) 2007 Elsevier Ltd. All rights reserved.
This paper gives the average distance analysis for the Euclidean tree constructed by a simple greedy but efficient algorithm of the on-line Steiner tree problem. The algorithm accepts the data one by one following the...
详细信息
This paper gives the average distance analysis for the Euclidean tree constructed by a simple greedy but efficient algorithm of the on-line Steiner tree problem. The algorithm accepts the data one by one following the order of input sequence. When a point arrives, the algorithm adds the shortest edge, between the new point and the points arriving already, to the previously constructed tree to form a new tree. We first show that, given n points uniformly on a unit disk in the plane, the expected Euclidean distance between a point and its j(th) (1 less than or equal to j less than or equal to n - 1) nearest neighbor is less than or equal to (5/3)root/j/n when n is large. Based upon this result, we show that the expected length of the tree constructed by the on-line algorithm is not greater than 4.34 times the expected length of the minimum Steiner tree when the number of input points is large.
We present original average-case results on the performance of the Ford-Fulkerson maxflow algorithm on grid graphs (sparse) and random geometric graphs (dense). The analysis technique combines experiments with probabi...
详细信息
We present original average-case results on the performance of the Ford-Fulkerson maxflow algorithm on grid graphs (sparse) and random geometric graphs (dense). The analysis technique combines experiments with probability generating functions, stochastic context free grammars and an application of the maximum likelihood principle enabling us to make statements about the performance, where a purely theoretical approach has little chance of success. The methods lends itself to automation allowing us to study more variations of the Ford-Fulkerson maxflow algorithm with different graph search strategies and several elementary operations. A simple depth-first search enhanced with random iterators provides the best performance on grid graphs. For random geometric graphs a simple priority-first search with a maximum-capacity heuristic provides the best performance. Notable is the observation that randomization improves the performance even when the inputs are created from a random process.
Permuting in place has been first analyzed by Knuth. It uses the cycle structure of the permutation. The elements of an array to be permuted are only moved when one sees a cycle leader (smallest element in its cycle)....
详细信息
Permuting in place has been first analyzed by Knuth. It uses the cycle structure of the permutation. The elements of an array to be permuted are only moved when one sees a cycle leader (smallest element in its cycle). So the essential part of such an algorithm is to test an element i about whether it is a cycle leader. Recently, Keller [Inform. Process. Lett. 81 (2002) 119-125] introduced two stopping rules: "If the last cycle leader has been detected, all elements have been moved, and no further tests are necessary" (heuristic 1), respectively "If only r elements have not been moved, then proceeding along a cycle is only useful for r steps" (heuristic 2). We analyze the average costs of these modifications applied to the standard algorithm of Knuth;they are (n + 2)H-n - 5n/2 - 1/2 similar to n log n and respectively ((2n + 1)/4)H[(n+1)/2] + (1/2)H2[(n+1)/2]-(1/2)([(n+1)/2]-[n/2]) - (n+1)/2 similar to (n/2) log n, as opposed to (n+1)H-n-2n similar to n log n in the classical case. (C) 2004 Elsevier Inc. All rights reserved.
作者：
Fukagawa, DAkutsu, TKyoto Univ
Dept Intelligence Sci & Technol Grad Sch Informat Kyoto 6068501 Japan Kyoto Univ
Bioinformat Ctr Inst Chem Res Kyoto 6110011 Japan
We analyzed average case performance of a known greedy algorithm for inference of a Boolean function from positive and negative examples, and gave a proof to an experimental conjecture that the greedy algorithm works ...
详细信息
We analyzed average case performance of a known greedy algorithm for inference of a Boolean function from positive and negative examples, and gave a proof to an experimental conjecture that the greedy algorithm works optimally with high probability if both input data and the underlying function are generated uniformly at random. (C) 2004 Elsevier B.V. All rights reserved.
Given the intersection points of a planar Jordan curve with the x-axis in the order in which they occur along the curve, sort them into the order in which they occur along the x-axis. In this paper, the average-case a...
详细信息
Given the intersection points of a planar Jordan curve with the x-axis in the order in which they occur along the curve, sort them into the order in which they occur along the x-axis. In this paper, the average-case analysis of a new simple algorithm that solves the above-mentioned problem is presented. A certain model of generating random Jordan sequences is introduced. The results of the analysis are summarised in the form of theorems that specify the conditions under which the algorithm runs in linear expected time. The results are verified experimentally by a computer simulation. (C) 1999 Elsevier Science B.V. All rights reserved.
A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main fin...
详细信息
A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main findings show that asymptotically, as the number of keys n tends to infinity, the average depth becomes ED(n) approximately 1/*** n + c', and the variance is var D(n) approximately alpha log n + c", where h1 is the entropy of the (Markovian-dependent) alphabet, and alpha is a parameter of the probabilistic model. The symmetric independent model has alpha = 0, hence in this case var D(n) = O(1). Limiting distribution is also derived for the depth D(n), and in particular, it is shown that D(n) tends to the normal distribution in all cases except the symmetric independent model. These results extend all previous analyses since most of them have been limited to independent models.
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.
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.
暂无评论