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

A fast distributed approximation algorithm for minimum spanning trees

DISTRIBUTED COMPUTING 2008年第6期20卷 391-402页

作者： Khan, Maleq Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Omega(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H is an element of [1, Theta(log n)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal (O) over tilde (D(G)) time.

关键词： minimum spanning tree distributed approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Club theory of the Grid

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2006年第14期18卷 1759-1773页

作者： Shi, Yao Lau, Francis C. M. Tse, Savio S. H. Du, Zhi-Hui Tang, Rui-Chun Li, San-Li Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The Grid is a new type of resource sharing infrastructure. Due to software and hardware limitations, the service that a certain Grid can offer is finite, and so is the number of users it can accommodate. If the number of users is too small, much of the planned resources would be wasted. On the other hand, excessive loading due to too many users could substantially reduce the benefit enjoyed by each user and also the efficiency of the Grid service. Therefore, there are two main problems for Grid design. (1) How many users should the Grid serve so that each user can receive the maximum benefit? (2) To a certain group of users, how much resources should be invested so that the construction and maintenance of the Grid become viable? Based on the economic theory of clubs, this paper gives a quantitative analysis of the quasi-optimal number of users and amount of each resource by regarding Grid services and resources as club goods. Based on our assumptions on the system model, we deduce two preliminary results and verify them by experiments using GridFTP. These two results allow the users to run randomized algorithms to achieve better system performance. Copyright (c) 2006 John Wiley & Sons, Ltd.

关键词： Grid computing club theory cost-benefit analysis randomized algorithm probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

Medial axis computation for planar free-form shapes

引用

COMPUTER-AIDED DESIGN 2009年第5期41卷 339-349页

作者： Aichholzer, O. Aigner, W. Aurenhammer, F. Hackl, T. Juettler, B. Rabl, M. Johannes Kepler Univ Linz A-4040 Linz Austria Graz Univ Technol A-8010 Graz Austria

We present a simple, efficient, and stable method for computing-with any desired precision-the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Planar shape Biarc approximation Medial axis Stability Divide & conquer randomized algorithm Numerical robustness

来源：评论

学校读者我要写书评

暂无评论

A Butterfly-Based Direct Integral-Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering From Electrically Large Conducting Objects

引用

IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION 2017年第9期65卷 4742-4750页

作者： Guo, Han Liu, Yang Hu, Jun Michielssen, Eric Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Elect Sci & Technol China Dept Microwave Engn Chengdu 611731 Sichuan Peoples R China

A butterfly-based direct combined-field integralequation (CFIE) solver for analyzing scattering from electrically large, perfect electrically conducting objects is presented. The proposed solver leverages the butterfly scheme to compress blocks of the hierarchical LU-factorized discretized CFIE operator and uses randomized butterfly reconstruction schemes to expedite the factorization. The memory requirement and computational cost of the direct butterfly-CFIE solver scale as O(N log(2) N) and O(N-1.5 log N), respectively. These scaling estimates permit significant memory and CPU savings when compared to those realized by low-rank decomposition-based solvers. The efficacy and accuracy of the proposed solver are demonstrated through its application to the analysis of scattering from canonical and realistic objects involving up to 14 million unknowns.

关键词： Butterfly scheme fast direct solver integral equations multilevel matrix decomposition algorithm randomized algorithm scattering

来源：评论

学校读者我要写书评

暂无评论

Exact simulation of diffusion first exit times: algorithm acceleration.

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2022年第1期23卷 1-20页

作者： Herrmann, Samuel Zucca, Cristina Univ Bourgogne Franche Inst Math Bourgogne IMB UMR 5584 CNRS F-21000 Dijon France Univ Torino Dept Math G Peano Via Carlo Alberto 10 I-10123 Turin Italy

In order to describe or estimate different quantities related to a specific random variable, it is of prime interest to numerically generate such a variate. In specific situations, the exact generation of random variables might be either momentarily unavailable or too expensive in terms of computation time. It therefore needs to be replaced by an approximation procedure. As was previously the case, the ambitious exact simulation of first exit times for diffusion processes was unreachable though it concerns many applications in different fields like mathematical finance, neuroscience or reliability. The usual way to describe first exit times was to use discretization schemes, that are of course approximation procedures. Recently, Herrmann and Zucca (Herrmann and Zucca, 2020) proposed a new algorithm, the so-called GDET-algorithm (General Diffusion Exit Time), which permits to simulate exactly the first exit time for one-dimensional diffusions. The only drawback of exact simulation methods using an acceptance-rejection sampling is their time consumption. In this paper the authors highlight an acceleration procedure for the GDET-algorithm based on a multi-armed bandit model. The efficiency of this acceleration is pointed out through numerical examples.

关键词： Exit time Brownian motion diffusion processes rejection sampling exact simulation multi-armed bandit randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Neighborhood Rendezvous

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第3期E105D卷 597-610页

作者： Eguchi, Ryota Kitamura, Naoki Izumi, Taisuke Nagoya Inst Technol Nagoya Aichi 4668555 Japan Osaka Univ Suita Osaka 5650871 Japan

In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Delta) rounds (Delta is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Delta) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(root n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within (O) over tilde( root n Delta/delta + n/delta) rounds for graphs of the minimum degree larger than root n, where n is the number of vertices in the graph, and delta is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves (O) over tilde (n/root delta)-round time complexity without using whiteboards. These algorithms attain o(Delta)-round complexity in the case of delta = omega(root n log n) and delta = omega(n(2/3) log(4/3) n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Omega(n)-round lower bound if either one of them is removed.

关键词： rendezvous randomized algorithm sublinear-time algorithm whiteboards

来源：评论

学校读者我要写书评

暂无评论

A fast, accurate, and simple method for pricing European-Asian and Saving-Asian options

引用

algorithmICA 2005年第2期42卷 141-158页

作者： Ohta, K Sadakane, K Shioura, A Tokuyama, T DC Card Co Ltd Tokyo Japan Kyushu Univ Grad Sch Informat Sci & Elect Engn Fukuoka 8128581 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We propose an efficient and accurate randomized approximation algorithm for computing the price of European-Asian options. Our algorithm can be seen as a modification of the approximation algorithm developed by Aingworth et al. (2000) into a randomized algorithm, which improves the accuracy theoretically as well as practically. We also propose a new option named the Saving-Asian option which enjoys advantages of both the European-Asian and American-Asian options. It is shown that our approximation algorithm also works for pricing Saving-Asian options.

关键词： approximation algorithm randomized algorithm option pricing Asian option binomial tree model

来源：评论

学校读者我要写书评

暂无评论

Fisher scoring: An interpolation family and its Monte Carlo implementations

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2010年第7期54卷 1744-1755页

作者： Wang, Yong Univ Auckland Dept Stat Auckland 1 New Zealand

The Fisher scoring method is widely used for likelihood maximization, but its application can be difficult in situations where the expected information matrix is not available in closed form or when parameters have constraints In this paper, we describe an interpolation family that generalizes the Fisher scoring method and propose a general Monte Carlo approach that makes these generalized methods also applicable in such situations. With this approach, random samples are generated from the iteratively estimated models and used to provide estimates of the expected information As a result, the likelihood function can be optimized by repeatedly solving weighted linear regression problems Specific extensions of this general approach to fitting multivariate normal mixtures and to fitting mixed-effects models with a single discrete random effect are also described. Numerical studies show that the proposed algorithms are fast and reliable to use, as compared with the classical expectation-maximization algorithm (C) 2010 Elsevier B V All rights reserved

关键词： Fisher information Fisher scoring Iteratively reweighted least squares EM algorithm Mixed-effects model Mixture model randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

SVD-based algorithms for fully-connected tensor network decomposition

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第5期43卷 1-23页

作者： Wang, Mengyu Li, Hanyu Chongqing Univ Coll Math & Stat Chongqing Peoples R China Chongqing Univ Key Lab Nonlinear Anal & its Applicat Minist Educ Beijing Peoples R China

The popular fully-connected tensor network (FCTN) decomposition has achieved successful applications in many fields. A standard method to this decomposition is the alternating least squares. However, it often converges slowly and suffers from issues of numerical stability. In this work, we investigate the SVD-based algorithms for FCTN decomposition to tackle the aforementioned deficiencies. On the basis of a result about FCTN-ranks, a deterministic algorithm, namely FCTN-SVD, is first proposed, which can approximate the FCTN decomposition under a fixed accuracy. Then, we present the randomized version of the algorithm. Both synthetic and real data are used to test our algorithms. Numerical results show that they perform much better than the existing methods, and the randomized algorithm can indeed yield acceleration on FCTN-SVD. Moreover, we also apply our algorithms to tensor-on-vector regression and achieve quite decent performance.

关键词： Fully-connected tensor network decomposition SVD randomized algorithm Alternating least squares Sketching

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for min-max 2-cluster editing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期34卷 47-63页

作者： Chen, Li-Hsuan Wu, Bang Ye Natl Chung Cheng Univ Chiayi 621 Taiwan

For a given graph and an integer t, the Min-Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for , where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let . We show that the problem is polynomial-time solvable when roughly . When , we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in time for and in time for , where .

关键词： Parameterized algorithm Parameterized complexity Graph modification Clustering randomized algorithm Subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：