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

Information-Theoretic Thresholds for Planted Dense Cycles

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第2期71卷 1266-1282页

作者： Mao, Cheng Wein, Alexander S. Zhang, Shenduo Georgia Inst Technol Sch Math Atlanta GA 30332 USA Univ Calif Davis Dept Math Davis CA 95616 USA

We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth n tau , representing the hidden one-dimensional geometry of vertices, is planted in an ambient random graph on n vertices. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of n, tau , and an edge-wise signal-to-noise ratio lambda . In particular, the information-theoretic thresholds differ from the computational thresholds established in a recent work for low-degree polynomial algorithms, thereby justifying the existence of statistical-to-computational gaps for this problem.

关键词： Information theory Image edge detection Polynomials Biological system modeling Bandwidth Computational efficiency Signal to noise ratio Geometry Prediction algorithms Lower bound Random graphs network theory graphs and networks information theory statistics geometrical problems and computations computations on discrete structures

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for the interval location problem with range constraints on length and average

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2008年第2期5卷 281-290页

作者： Hsieh, Yong-Hsiang Yu, Chih-Chiang Wang, Biing-Feng Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan

Let A be a sequence of n real numbers, L-1 and L-2 be two integers such that L-1 <= L-2, and let R-1 and R-2 be two real numbers such that R-1 <= R-2. An interval of A is feasible if its length is between L-1 and L-2, and its average is between R-1 and R-2. In this paper, we study the following problems: finding all feasible intervals of A, counting all feasible intervals of A, finding a maximum cardinality set of nonoverlapping feasible intervals of A, locating a longest feasible interval of A, and locating a shortest feasible interval of A. The problems are motivated from the problem of locating CpG islands in biomolecular sequences. In this paper, we first show that all the problems have an Omega(n log n)-time lower bound in the comparison model. Then, we use geometric approaches to design optimal algorithms for the problems. All the presented algorithms run in an online manner and use O(n) space.

关键词： algorithms data structures analysis of algorithms geometrical problems and computations

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Computing Geodesic Distances in Tree Space

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第1期8卷 2-13页

作者： Owen, Megan Provan, J. Scott Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ N Carolina Dept Stat & Operat Res Chapel Hill NC 27599 USA

Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.

关键词： geometrical problems and computations trees graph theory biology and genetics phylogenetics distance

来源：评论

学校读者我要写书评

暂无评论

Visualization of Spatiotemporal Behavior of Discrete Maps via Generation of Recursive Median Elements

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2010年第2期32卷 378-384页

作者： Sagar, B. S. Daya Indian Stat Inst Bangalore Ctr Syst Sci & Informat Unit Bangalore 560059 Karnataka India

Spatial interpolation is one of the demanding techniques in Geographic Information Science (GISci) to generate interpolated maps in a continuous manner by using two discrete spatial and/or temporal data sets. Noise-free data (thematic layers) depicting a specific theme at varied spatial or temporal resolutions consist of connected components either in aggregated or in disaggregated forms. This short paper provides a simple framework: 1) to categorize the connected components of layered sets of two different time instants through their spatial relationships and the Hausdorff distances between the companion-connected components and 2) to generate sequential maps (interpolations) between the discrete thematic maps. Development of the median set, using Hausdorff erosion and dilation distances to interpolate between temporal frames, is demonstrated on lake geometries mapped at two different times and also on the bubonic plague epidemic spread data available for 11 consecutive years. We documented the significantly fair quality of the median sets generated for epidemic data between alternative years by visually comparing the interpolated maps with actual maps. They can be used to visualize (animate) the spatiotemporal behavior of a specific theme in a continuous sequence.

关键词： GISci spatial interpolation mathematical morphology thematic maps dilation erosion interpolation formulas spatial databases and GIS cartography morphological image representation visualization techniques and methodologies geometrical problems and computations set theory

来源：评论

学校读者我要写书评

暂无评论

Linear Algorithms in Sublinear Time-a Tutorial on Statistical Estimation

引用

IEEE COMPUTER GRAPHICS AND APPLICATIONS 2011年第2期31卷 58-66页

作者： Ullrich, Torsten Fellner, Dieter W. Fraunhofer Austria Res Vienna Austria

This tutorial presents probability theory techniques for boosting linear algorithms. The approach is based on statistics and uses educated guesses instead of comprehensive calculations. Because estimates can be calcul... 详细信息

关键词： Tutorial Probability Time Sharing Computer Systems Statistics Image Processing Maximum Likelihood Estimation Computer Graphics Visualization Image Reconstruction Image Sampling Graphics And Multimedia computations On Discrete Structures geometrical problems and computations Statistical Computing Computer Graphics

来源：评论

学校读者我要写书评

暂无评论

New scheduling strategies for randomized incremental algorithms in the context of speculative parallelization

引用

IEEE TRANSACTIONS ON COMPUTERS 2007年第6期56卷 839-852页

作者： Llanos, Diego R. Orden, David Palop, Belen Univ Valladolid Dept Informat Edif Tecn Informat Valladolid 47011 Spain Univ Alcala de Henares Fac Ciencias Dept Matemat E-28871 Alcala De Henares Madrid Spain

In this work, we address the problem of scheduling loops with dependences in the context of speculative parallelization. We show that the scheduling alternatives are highly influenced by the dependence violation pattern the code presents. We center our analysis in those algorithms where dependences are less likely to appear as the execution proceeds. Particularly, we focus on randomized incremental algorithms, widely used as a much more efficient solution to many problems than their deterministic counterparts. These important algorithms are, in general, hard to parallelize by hand and represent a challenge for any automatic parallelization scheme. Our analysis led us to the development of MESETA, a new scheduling strategy that takes into account the probability of a dependence violation to determine the number of iterations being scheduled. MESETA is compared with existing techniques, including Fixed-Size Chunking (FSC), the only scheduling alternative used so far in the context of speculative parallelization. Our experimental results show a 5.5 percent to 36.25 percent speedup improvement over FSC, leading to a better extraction of the parallelism inherent to randomized incremental algorithms. Moreover, when the cost of dependence violations is too high to obtain speedups, MESETA curves the performance degradation.

关键词： parallelism and concurrency load balancing and task assignment scheduling and task partitioning geometrical problems and computations

来源：评论

学校读者我要写书评

暂无评论

Toward a Robust Search Method for the Protein-Drug Docking Problem

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第4期8卷 1120-1133页

作者： Sadjad, Bashir S. Zsoldos, Zsolt Univ Waterloo Sch Comp Sci Waterloo ON N2V2X4 Canada Simulated Biomol Syst Waterloo ON N2V2X4 Canada Simulated Biomol Syst Unit 520 Toronto ON M9W6V1 Canada

Predicting the binding mode(s) of a drug molecule to a target receptor is pivotal in structure-based rational drug design. In contrast to most approaches to solve this problem, the idea in this paper is to analyze the search problem from a computational perspective. By building on top of an existing docking tool, new methods are proposed and relevant computational results are proven. These methods and results are applicable for other place-and-join frameworks as well. A fast approximation scheme for the docking of rigid fragments is described that guarantees certain geometric approximation factors. It is also demonstrated that this can be translated into an energy approximation for simple scoring functions. A polynomial time algorithm is developed for the matching phase of the docked rigid fragments. It is demonstrated that the generic matching problem is NP-hard. At the same time, the optimality of the proposed algorithm is proven under certain scoring function conditions. The matching results are also applicable for some of the fragment-based de novo design methods. On the practical side, the proposed method is tested on 829 complexes from the PDB. The results show that the closest predicted pose to the native structure has the average RMS deviation of 1.06 angstrom.

关键词： Life and medical sciences biology and genetics geometrical problems and computations curve, surface, solid and object representations bioinformatics (genome or protein) databases

来源：评论

学校读者我要写书评

暂无评论

A linear time approximation scheme for Euclidean TSP

A linear time approximation scheme for Euclidean TSP

引用

IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bartal, Yair Gottlieb, Lee-Ad Hebrew Univ Jerusalem Jerusalem Israel Ariel Univ Israeli 40700 Israel

ISBN: (纸本)9780769551357

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of O-d,O-e(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime O-d,O-e(n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].

关键词： computations on discrete structures geometrical problems and computations

来源：评论

学校读者我要写书评

暂无评论

A linear algorithm for eliminating hidden-lines from a polygonal cylinder

引用

The Visual Computer 1986年第1期2卷 44-53页

作者： Rappaport, David School of Computer Science McGill University Montreal H3A 2K6 Quebec 805 Sherbroke St. West Canada

A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity of O(n²). It is the interent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications. © 1986 Springer-Verlag.

关键词： Computational Geometry Geometric algorithms geometrical problems and computations Nonnumerical Algorithms and problems Three-Dimensional Graphics and Realism Visible line/surface elimination

来源：评论

学校读者我要写书评

暂无评论

Approximate topological matching of quadrilateral meshes

Approximate topological matching of quadrilateral meshes

引用

IEEE International Conference on Shape Modeling and Applications

作者： Eppstein, David Goodrich, Michael T. Kim, Ethan Tamstorf, Rasmus Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA McGill Univ Sch Comp Sci Montreal PQ H3A 2T5 Canada Walt Disney Animat Studios Burbank CA USA

ISBN: (纸本)9781424422609

We study approximate topological matching of quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in graphics that involve shape modeling whose results need to be merged in order to produce a final unified representation of an object. We show that the problem of producing a maximum approximate topological match of two quad meshes in NP-hard. Given this result, which makes an exact solution extremely unlikely, we show that the natural greedy algorithm derived from polynomial-time graph isomorphism can produce poor results, even when it is possible to find matches with only a few non-matching quads. Nevertheless, we provide a "lazy-greedy" algorithm that is guaranteed to find good matches when mis-matching portions of mesh are localized. Finally, we provide empirical evidence that this approach produces good matches between similar quad meshes.

关键词： F.2.2 [analysis of algorithms and problem complexity]: nonnumerical algorithms and problems geometrical problems and computations I.3.5 [computer graphics]: computational geometry and object modeling boundary representations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：