检索结果-内蒙古大学图书馆

A note on point location in delaunay triangulations of random points

ALGORITHMICA 1998年第4期22卷 477-482页

作者： Devroye, L Mucke, EP Zhu, BH McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada ANSYS Inc Houston PA 15342 USA City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Univ Calif Los Alamos Natl Lab Los Alamos NM 87545 USA

This short note considers the problem of point location in a Delaunay triangulation of n random points, using no additional preprocessing or storage other than a standard data structure representing the triangulation. A simple and easy-to-implement (but, of course, worst-case suboptimal) heuristic is shown to take expected time O(n(1/3)).

关键词： Voronoi diagram Delaunay triangulation point location probabilistic analysis of algorithms computational geometry

来源：评论

学校读者我要写书评

暂无评论

FAST NEAREST-NEIGHBOR SEARCH IN DISSIMILARITY SPACES

引用

IEEE TRANSACTIONS ON PATTERN analysis AND MACHINE INTELLIGENCE 1993年第9期15卷 957-962页

作者： FARAGO, A LINDER, T LUGOSI, G Technical University of Budapest Budapest Hungary

A fast nearest-neighbor algorithm is presented. It works in general spaces where the known cell (bucketing) techniques cannot be implemented for various reasons, such as the absence of coordinate structure and/or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. This paper provides an exact probabilistic analysis or this family of algorithms, proving its O(1) asymptotic average complexity measured in the number of dissimilarity calculations.

关键词： AVERAGE COMPLEXITY DISSIMILARITY SPACES FAST NEAREST-NEIGHBOR SEARCH PATTERN RECOGNITION probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards a Realistic analysis of the QuickSelect Algorithm

引用

THEORY OF COMPUTING SYSTEMS 2016年第4期58卷 528-578页

作者： Clement, Julien Fill, James Allen Thu Hien Nguyen Thi Vallee, Brigitte Univ Caen ENSICAEN GREYC CNRS UMR 6072 F-14032 Caen France Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA

We revisit the analysis of the classical QuickSelect algorithm. Usually, the analysis deals with the mean number of key comparisons, but here we view keys as words produced by a source, and words are compared via their symbols in lexicographic order. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. The "realistic" cost of the algorithm is here the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons. For the QuickSort algorithm, known average-case complexity results are of in the case of key comparisons, and for symbol comparisons. For QuickSelect algorithms, and with respect to key comparisons, the average-case complexity is I similar to(n). In this present article, we prove that, with respect to symbol comparisons, QuickSelect's average-case complexity remains I similar to(n). In each case, we provide explicit expressions for the dominant constants, closely related to the probabilistic behaviour of the source. We began investigating this research topic with Philippe Flajolet, and the short version of the present paper (the ICALP'2009 paper) was written with him. As usual, Philippe played a central role, notably on the following points: introduction of the QuickVal algorithm, tameness of sources, and use of Rice's method. He also made many experiments exhibiting the asymptotic slope rho(alpha) and plotted nice graphs, which are reproduced in this paper. Even though the extended abstract does not provide any proof of the analysis of the algorithm QuickQuant, Philippe also devised with us a precise plan for this proof which has now completely been written. For all these reasons, we could have added (and certainly would have liked to add) Philippe as a co-author of this paper. On the other hand, Ph

关键词： probabilistic analysis of algorithms Sorting and searching algorithms Selection problem Pattern matching Permutations Information theory Rice's method Asymptotic estimates Quickselect

来源：评论

学校读者我要写书评

暂无评论

A Bayesian Approach to Extracting Kinetic Information from Artificial Enzymatic Networks

引用

ANALYTICAL CHEMISTRY 2022年第20期94卷 7311-7318页

作者： Baltussen, Mathieu G. van de Wiel, Jeroen Regueiro, Cristina Lia Fernandez Jakstaite, Migle Huck, Wilhelm T. S. Radboud Univ Nijmegen Inst Mol & Mat NL-6525 AJ Nijmegen Netherlands

In order to create artificial enzymatic networks capable of increasingly complex behavior, an improved methodology in understanding and controlling the kinetics of these networks is needed. Here, we introduce a Bayesian analysis method allowing for the accurate inference of enzyme kinetic parameters and determination of most likely reaction mechanisms, by combining data from different experiments and network topologies in a single probabilistic analysis framework. This Bayesian approach explicitly allows us to continuously improve our parameter estimates and behavior predictions by iteratively adding new data to our models, while automatically taking into account uncertainties introduced by the experimental setups or the chemical processes in general. We demonstrate the potential of this approach by characterizing systems of enzymes compartmentalized in beads inside flow reactors. The methods we introduce here provide a new approach to the design of increasingly complex artificial enzymatic networks, making the design of such networks more efficient, and robust against the accumulation of experimental errors.

关键词： Kinetics Bayesian statistics probabilistic analysis of algorithms Bayesian analysis Uncertainty

来源：评论

学校读者我要写书评

暂无评论

Stochastic runtime analysis of a Cross-Entropy algorithm for traveling salesman problems

引用

THEORETICAL COMPUTER SCIENCE 2018年 724卷 69-86页

作者： Wu, Zijun Moehring, Rolf H. Lai, Jianhui BISEC Pingle Yuan 100 Beijing Peoples R China Beijing Univ Technol Coll Metropolitan Transportat Pingle Yuan 100 Beijing Peoples R China Beijing Univ Technol Sch Appl Math & Phys Beijing Peoples R China Berlin Univ Technol Math Berlin Germany

This article analyzes the stochastic runtime of a Cross-Entropy algorithm mimicking an Max-MM Ant System with iteration-best reinforcement. It investigates the impact of magnitude of the sample size on the runtime to find optimal solutions for TSP instances. For simple TSP instances that have a {1,n}-valued distance function and a unique optimal solution, we show that sample size N is an element of omega(Inn) results in a stochastically polynomial runtime, and N is an element of O(In n) results in a stochastically exponential runtime, where "stochastically" means with a probability of 1 - n(-omega(1)), and n represents number of cities. In particular, for N is an element of omega(In n), we prove a stochastic runtime of O(N . n(6)) with the vertex-based random solution generation, and a stochastic runtime of O(N . n(3) Inn) with the edge-based random solution generation. These runtimes are very close to the best known expected runtime for variants of Max-Min Ant System with best-so-far reinforcement by choosing a small N is an element of omega(In n). They are obtained for the stronger notion of stochastic runtime, and analyze the runtime in most cases. We also inspect more complex instances with n vertices positioned on an m x m grid. When the n vertices span a convex polygon, we obtain a stochastic runtime of O(n(4)m(3+is an element of)) with the vertex-based random solution generation, and a stochastic runtime of O(n(3)m(3+is an element of)) for the edge-based random solution generation. When there are k is an element of O(1) many vertices inside a convex polygon spanned by the other n k vertices, we obtain a stochastic runtime of O(n(4)m(5+is an element of) + n(6k-1)m(is an element of)) with the vertex-based random solution generation, and a stochastic runtime of O(n(3)m(5+is an element of) + n(3k)m(is an element of)) with the edge-based random solution generation. These runtimes are better than the expected runtime for the so-called (mu+lambda) EA reported in a r

关键词： probabilistic analysis of algorithms Stochastic runtime analysis of evolutionary algorithms Cross Entropy algorithm Max-MM Ant System (mu plus lambda) EA

来源：评论

学校读者我要写书评

暂无评论

On the k-orientability of random graphs

引用

DISCRETE MATHEMATICS 2009年第6期309卷 1476-1490页

作者： Devroye, Luc Malalla, Ebrahim King Fahd Univ Petr & Minerals Dept Informat & Comp Sci Dhahran 31261 Saudi Arabia McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

Let G(n, m) be an undirected random graph with n vertices and m multiedges that may include loops, where each edge is realized by choosing its two vertices independently and uniformly at random with replacement from the set of all n vertices. The random graph G(n, m) is said to be k-orientable, where k >= 2 is an integer, if there exists an orientation of the edges such that the maximum out-degree is at most k. Let c(k) = sup {c : G(n, cn) is k-orientable w.h.p.}. We prove that for k large enough, 1 - 2(k) exp (-k + 1 + e(-k/4)) < c(k)/k < 1 - exp (-2k (1 - e(-2k))), and the time c(k)n is a threshold for the emergence of a giant subgraph of size (-)(n) whose edges are more than k times its vertices. Other results are presented. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Random graphs k-orientability k-core Maximum density Static two-way chaining Off-line load balancing Competitive analysis probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding the largest triangle in a graph in expected quadratic time

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第2期286卷 458-467页

作者： Lancia, Giuseppe Vidoni, Paolo Univ Udine Dipartimento Matemat Informat & Fis I-33100 Udine Italy Univ Udine Dipartimento Sci Econ & Stat I-33100 Udine Italy

Finding the largest triangle in an n-nodes edge-weighted graph belongs to a set of problems all equivalent under subcubic reductions. Namely, a truly subcubic algorithm for any one of them would imply that they are all subcubic. A recent strong conjecture states that none of them can be solved in less than Theta(n(3)) time, but this negative result does not rule out the possibility of algorithms with average, rather than worst-case, subcubic running time. Indeed, in this work we describe the first truly-subcubic average complexity procedure for this problem for graphs whose edge lengths are uniformly distributed in [0,1]. Our procedure finds the largest triangle in average quadratic time, which is the best possible complexity of any algorithm for this problem. We also give empirical evidence that the quadratic average complexity holds for many other random distributions of the edge lengths. A notable exception is when the lengths are distances between random points in Euclidean space, for which the algorithm takes average cubic time. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Applied probability Combinatorial optimization Max weight triangle 3-OPT TSP neighborhood probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation of some NP-hard optimization problems by finite machines, in probability

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期259卷 323-339页

作者： Hong, DW Birget, JC Southwest State Univ Dept Math & Comp Sci Marshall MN 56258 USA Univ Nebraska Dept Comp Sci Lincoln NE 68588 USA

We introduce a subclass of NP optimization problems which contains some NP-hard problems, e.g., bin covering and bin packing. For each problem in this subclass we prove that with probability tending to 1 (exponentially fast as the number of input items tends to infinity), the problem is approximately up to any chosen relative error bound epsilon > 0 by a deterministic finite-state machine. More precisely, let Pi be a problem in our subclass of NP optimization problems, let epsilon > 0 be any chosen bound, and assume there is a fixed (but arbitrary) probability distribution for the inputs. Then there exists a finite-state machine which does the following: On an input I (random according to this probability distribution), the finite-state machine produces a feasible solution whose objective value M (I) satisfies [GRAPHICS] when n is large enough. Here k and h are positive constants. All rights reserved. (C) 2001 Elsevier Science B.V.

关键词： NP-optimization problems approximation probabilistic analysis of algorithms finite-state machines

来源：评论

学校读者我要写书评

暂无评论

ON LINEAR-PROGRAMS WITH RANDOM COSTS

引用

MATHEMATICAL PROGRAMMING 1986年第1期35卷 3-16页

作者： DYER, ME FRIEZE, AM MCDIARMID, CJH UNIV LONDON QUEEN MARY COLL DEPT COMP SCI & STATLONDON E1 4NSENGLAND UNIV OXFORD INST ECON & STATOXFORDENGLAND

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadrati... 详细信息

关键词： Random linear program probabilistic analysis of algorithms average complexity quadratic assignment problem branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults

引用

SIAM JOURNAL ON COMPUTING 1999年第1期29卷 258-273页

作者： Leighton, T Ma, YA MIT Dept Math Cambridge MA 02139 USA MIT Comp Sci Lab Cambridge MA 02139 USA

We study networks that can sort n items even when a large number of the comparators in the network are faulty. We restrict our attention to networks that consist of registers, comparators, and replicators. (Replicators are used to copy an item from one register to another, and they are assumed to be fault free.) We consider the scenario of both random and worst-case comparator faults, and we follow the general model of destructive comparator failure proposed by Assaf and Upfal [Proc. 31st IEEE Symposium on Foundations of Computer Science, St. Louis, MO, 1990, pp. 275-284] in which the two outputs of a faulty comparator can fail independently of each other. In the case of random faults, Assaf and Upfal showed how to construct a network with O(n log(2) n) comparators that (with high probability) can sort n items even if a constant fraction of the comparators are faulty. Whether the bound on the number of comparators can be improved (to, say, O(n log n)) for sorting (or merging) has remained an interesting open question. We resolve this question in this paper by proving that any n-item sorting or merging network which can tolerate a constant fraction of random failures has Omega(n log(2) n) comparators. In the case of worst-case faults, we show that Omega(kn log n) comparators are necessary to construct a sorting or merging network that can tolerate up to k worst-case faults. We also show that this bound is tight for k = O(log n). The lower bound is particularly significant since it formally proves that the cost of being tolerant to worst-case failures is very high. Both the lower bound for random faults and the lower bound for worst-case faults are the first nontrivial lower bounds on the size of a fault-tolerant sorting or merging network.

关键词： merging sorting circuits comparator networks fault-tolerance lower bounds probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：