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

Fixed parameter algorithms for the minimum weight triangulation problem

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2008年第3期18卷 185-220页

作者： Borgelt, Magdalene Grantson Borgelt, Christian Levcopoulos, Christos Dept Informat & Comp Sci NL-3508 TA Utrecht Netherlands European Ctr Soft Comp Mieres 33600 Spain Lund Univ Dept Comp Sci S-221 Lund Sweden

We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n - k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation.

关键词： minimum weight triangulation fixed parameter algorithm dynamic programming divide-and-conquer algorithm

来源：评论

学校读者我要写书评

暂无评论

Asymptotic distributions for Random Median Quicksort

引用

JOURNAL OF DISCRETE algorithmS 2007年第3期5卷 592-608页

作者： Okasha, H. M. Roesler, U. Al Azhar Univ Math Dept Cairo Egypt Christian Albrechts Univ Kiel Math Seminar D-24098 Kiel Germany

The first complete running time analysis of a stochastic divide and conquer algorithm was given for Quicksort, a sorting algorithm invented 1961 by Hoare. We analyse here the variant Random Median Quicksort. The analysis includes the expectation, the asymptotic distribution, the moments and exponential moments. The asymptotic distribution is characterized by a stochastic fixed point equation. The basic technic will be generating functions and the contraction method. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Quicksort Sorting algorithm Analysis of algorithm Recursive equation divide-and-conquer algorithm Stochastic fixed point equation Contraction method Euler differential equation

来源：评论

学校读者我要写书评

暂无评论

On the contraction method with degenerate limit equation

引用

ANNALS OF PROBABILITY 2004年第3B期32卷 2838-2856页

作者： Neininger, R Rüschendorf, L Univ Frankfurt Dept Math D-60325 Frankfurt Germany Univ Freiburg Inst Math Stochast D-79104 Freiburg Germany

A class of random recursive sequences (Y-n) with slowly varying variances as arising for parameters of random trees or recursive algorithms X leads after normalizations to degenerate limit equations of the form X =(L) X. For nondegenerate limit equations the contraction method is a main tool to establish convergence of the scaled sequence to the "unique" solution of the limit equation. In this paper we develop an extension of the contraction method which allows us to derive limit theorems for parameters of algorithms and data structures with degenerate limit equation. In particular, we establish some new tools and a general convergence scheme, which transfers information on mean and variance into a central limit law (with normal limit). We also obtain a convergence rate result. For the proof we use selfdecomposability properties of the limit normal distribution which allow us to mimic the recursive sequence by an accompanying sequence in normal variables.

关键词： contraction method analysis of algorithms recurrence recursive algorithms divide-and-conquer algorithm random recursive structures Zolotarev metric

来源：评论

学校读者我要写书评

暂无评论

A PROBABLY FAST, PROVABLY OPTIMAL algorithm FOR RECTILINEAR STEINER TREES

引用

RANDOM STRUCTURES & algorithmS 1994年第4期5卷 535-557页

作者： DENEEN, LL SHUTE, GM THOMBORSON, CD Department of Computer Science University of Minnesota Duluth MN 55812

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all epsilon > 0, there exists b > 0 such that Prob[T(n) < 2b square-root n log n] > 1 - epsilon, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. (C) 1994 John Wiley & Sons, Inc.

关键词： Steiner tree rectilinear Steiner tree divide-and-conquer algorithm computational geometry probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast method for variable-order space-fractional diffusion equations

引用

NUMERICAL algorithmS 2020年第4期85卷 1519-1540页

作者： Jia, Jinhong Zheng, Xiangcheng Fu, Hongfei Dai, Pingfei Wang, Hong Shandong Normal Univ Sch Math & Stat Jinan 250358 Shandong Peoples R China Univ South Carolina Dept Math Columbia SC 29208 USA China Univ Petr Coll Sci Qingdao 266580 Peoples R China Zhejiang Univ Sch Math Sci Hangzhou 310027 Zhejiang Peoples R China

We develop a fast divide-and-conquer indirect collocation method for the homogeneous Dirichlet boundary value problem of variable-order space-fractional diffusion equations. Due to the impact of the space-dependent variable order, the resulting stiffness matrix of the numerical scheme does not have a Toeplitz structure. In this paper, we derive a fast approximation of the coefficient matrix by the means of a finite sum of Toeplitz matrices multiplied by diagonal matrices. We show that the approximation is asymptotically consistent with the original problem, which requires O(Nlog2N)\ memory and O(Nlog3N) computational complexity with N being the numbers of unknowns. Numerical experiments are presented to demonstrate the effectiveness and the efficiency of the proposed method.

关键词： Variable-order space-fractional diffusion equation Collocation method divide-and-conquer algorithm Toeplitz matrix

来源：评论

学校读者我要写书评

暂无评论

A Subdivision Method of Flight Phases Based on divide-and-conquer Gaussian Mixture Model

引用

IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT 2023年 72卷 1页

作者： Wang, Yuan Wang, Benkuan Liu, Datong Harbin Inst Technol Sch Elect & Informat Engn Harbin 150080 Peoples R China

Monitoring the flight status of aircraft is crucial for ensuring safe and reliable flights. A global monitoring model is a commonly used method to adapt to the monitoring of whole flight process. However, the global monitoring model does not accurately capture the features when the distribution of flight data is dynamically transformed with flight phases, which affects the performance of the model. Therefore, it is essential to subdivide the data into different flight phases by analyzing distributions before building the monitoring model. In view of this, this article proposes the divide-and-conquer Gaussian mixture model (DcGMM) method for a subdivision of flight phases. To improve the division performance of complex flight phases, the proposed method divides the subdivision task into independent subtasks based on both longitudinal and lateral aircraft motion. Then, separately conquer problems of both subtasks based on Gaussian mixture model (GMM) models, not only to divide general flight phases by clustering but also to divide transition phases by using probabilities generated from GMM with optimization thresholds. Finally, combine division results of both subtasks, and a boundary-based flight phase correction method is designed for decreasing misclassified phases to achieve a high-performance subdivision. In summary, a new high-precision subdivision method for complex flight phases is proposed in this article. This article validates the performance of the proposed method experimenting on NASA public datasets from flight recorded data. Compared with state-of-the-art methods, the proposed method demonstrates higher performance by the accuracy and macro F1 score.

关键词： Aviation safety divide-and-conquer algorithm flight phase subdivision flight status monitoring Gaussian mixture model (GMM)

来源：评论

学校读者我要写书评

暂无评论

Adaptive Strategy and Decision Making Model for Sensing-Based Network Applications 19

Adaptive Strategy and Decision Making Model for Sensing-Base...

引用

19th International Symposium on Communications and Information Technologies (ISCIT)

作者： Ibrahim, Marwa Harb, Hassan Nasser, Abbass Mansour, Ali Osswald, Christophe ENSTA Bretagne CNRS UMR 6285 Lab STICC Brest France Amer Univ Culture & Educ AUCE Comp Sci Dept Beirut Lebanon

ISBN: (纸本)9781728150093

Energy conservation and decision making are at the heart of wireless sensor network (WSN) research. Indeed, the limited power of sensors, which is mostly not rechargeable, accompanied to the dense deployment of sensors, which collect a huge amount of data, complicate the makers' decision. In this paper, we propose an energy-efficient adaptive strategy and decision making technique based on a grid architecture of WSN, where a Grid-Leader (GL) is assigned for each grid. Our technique works on the three tiers of WSN: sensors, grid-leader (GL) and sink. At the first tier, each sensor applies a divide-and-conquer algorithm in order to send a reduced set of data to its appropriate GL;At the second tier, the GL combines data coming from sensors and sends useful information, i.e. satisfying a confidence threshold, about the monitored grid to the sink. The last tier, e.g. sink node, introduces two decision tables (score and early decisions) in order to make a real-time decision for each grid in the network. Extensive simulations on real sensor data demonstrated that our technique can be efficiently saving the network energy and helping in taking decisions, while maintaining an acceptable data accuracy level.

关键词： Wireless Sensor Networks (WSNs) Data Reduction Grid Topology divide-and-conquer algorithm Support-Confidence Method Decision Making Model

来源：评论

学校读者我要写书评

暂无评论

An Efficient Solution Method for Multibody Systems with Loops Using Multiple Processors 6

An Efficient Solution Method for Multibody Systems with Loop...

引用

6th International Conference on Automation, Robotics and Applications (ICARA)

作者： Ghosh, Tushar K. Nguyen, Luong A. Quiocho, Leslie J. Natl Secur Solut Commun L 3 Houston TX 77058 USA NASA Software Robot & Simulat Div Johnson Space Ctr Houston TX USA

ISBN: (纸本)9781479964666

This paper describes a multibody dynamics algorithm formulated for parallel implementation on multiprocessor computing platforms using the divide-and-conquer approach. The system of interest is a general topology of rigid and elastic articulated bodies with or without loops. The algorithm divides the multibody system into a number of smaller sets of bodies in chain or tree structures, called "branches" at convenient joints called "connection points", and uses an Order-N (O (N)) approach to formulate the dynamics of each branch in terms of the unknown spatial connection forces. The equations of motion for the branches, leaving the connection forces as unknowns, are implemented in separate processors in parallel for computational efficiency, and the equations for all the unknown connection forces are synthesized and solved in one or several processors. The performances of two implementations of this divide-and-conquer algorithm in multiple processors are compared with an existing method implemented on a single processor.

关键词： Multibody dynamics multiple processors divide-and-conquer algorithm computational efficiency Order-N

来源：评论

学校读者我要写书评

暂无评论

An adaptive lack of fit test for big data

引用

Statistical Theory and Related Fields 2017年第1期1卷 59-68页

作者： Yanyan Zhao Changliang Zou Zhaojun Wang Institute of Statistics and LPMC Nankai UniversityTianjinChina

New technological advancements combined with powerful computer hardware and high-speed network make big data *** massive sample size of big data introduces unique computational challenges on scalability and storage of statistical *** this paper,we focus on the lack of fit test of parametric regression models under the framework of big *** develop a computationally feasible testing approach via integrating the divide-and-conquer algorithm into a powerful nonparametric test *** theory results show that under mild conditions,the asymptotic null distribution of the proposed test is standard ***,the proposed test benefits fromthe use of data-driven bandwidth procedure and thus possesses certain adaptive *** studies show that the proposed method has satisfactory performances,and it is illustrated with an analysis of an airline data.

关键词： Adaptive test asymptotic distribution divide-and-conquer algorithm massive dataset model specification test

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer method to improve performance in quantum transport calculations: conductance in rotated graphene nanoribbons side-contact junctions

引用

ELECTRONIC STRUCTURE 2022年第4期4卷 047001-047001页

作者： Rodriguez, Mauricio J. Ramirez, Carlos Univ Nacl Autonoma Mexico Fac Ciencias Dept Fis Apartado Postal 70-542 Ciudad De Mexico 04510 Mexico

We propose a divide-and-conquer algorithm to find recursively the scattering matrix of general tight-binding structures. The scattering matrix allows a direct calculation of transport properties in mesoscopic systems by using the Landauer formula. The method is exact, and by analyzing the performance of the algorithm in square, triangular and honeycomb lattices, we show a significant improvement in comparison to other state-of-the-art recursive and non-recursive methods. We utilize this algorithm to compute the conductance of a rotated graphene nanoribbon side-contact junction, revealing that for electrons with energies smaller than -2.7 eV the transmission function depends negligibly on the angle of the junction, whereas for electrons with energies greater than -2.7 eV, there exists a set of angles for the system that increase its conductance independently of the energy of the particles.

关键词： quantum transport Landauer conductance scattering matrix recursive methods divide-and-conquer algorithm side-contact graphene

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：