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

Large-Scale Log-Determinant Computation via Weighted L₂ Polynomial Approximation with Prior Distribution of Eigenvalues 1

引用

3rd International Conference on High-Performance Computing and Applications (HPCA)

作者： Peng, Wei Wang, Hongxia Natl Univ Def Technol Coll Sci Sanyi Ave Changsha 410073 Hunan Peoples R China

ISBN: (数字)9783319325576

ISBN: (纸本)9783319325576;9783319325569

Since the classic determinant computation method Cholesky decomposition may devastate sparsity of matrices and cost cubic steps, it is impractical to apply this method to large-scale symmetric positive-definite matrices due to limitation of storage and efficiency. Therefore, a randomized algorithm is proposed to calculate log-determinants of symmetric positive-definite matrices via stochastic trace approximations, implemented by weighted L-2 orthogonal polynomial expansions with efficient recursion formulas and matrix-vector multiplications based on the matrix eigenvalue distribution. As Chebyshev expansions have been applied to this problem before, our main contribution is proposing the strategies of weighted function selection based on prior eigenvalue distribution, which generalizes approximating polynomials for this problem and may accelerate computation.

关键词： Log-determinant Best approximation Eigenvalue distribution randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Robust Control Method for a Small UAV with Bounded Uncertainty 35

A Probabilistic Robust Control Method for a Small UAV with B...

引用

第35届中国控制会议

作者： XIE Rong WANG Xinmin WANG Jian CAO Yuyan LI Ting School of Automation Northwestern Polytechnical University

ISBN: (纸本)9781509009107

This paper proposes a probabilistic robust control approach for a small unmanned aerial vehicle(UAV) in longitudinal ight. In the proposed method, the stochastic behavior of uncertainty parameters is considered in solving a high-performance robust controller of UAV. Compared to deterministic robust control, this solution has two advantages:(a) the controller obtained by the proposed method has xed order;(b) it is less-conservative and more reasonable for controlling ight control systems with bounded uncertainty. Simulation results for an UAV in longitudinal motion are given to show the effectiveness of the proposed approach.

关键词： Probabilistic robust control Flight Control Bounded uncertainty randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Constant-Factor Approximation algorithm for Planar Visibility Counting Problem 22nd

An Improved Constant-Factor Approximation Algorithm for Plan...

引用

22nd International Computing and Combinatorics Conference (COCOON)

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Sharif Univ Technol Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran

ISBN: (纸本)9783319426341;9783319426334

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can trivially be solved in logarithmic query time using O(n(4)) preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a trade-off between the space and the query time. They answer any query in O epsilon(n (1-alpha)) with O epsilon (n(2+2 alpha)) of preprocessing time and space, where alpha is a constant 0 <= alpha <= 1, epsilon > 0 is another constant that can be made arbitrarily small, and O epsilon(f(n)) = O(f( n)n(epsilon)). In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants 0 <= beta <= 2/3 and 0 < delta < 1, the expected preprocessing time, the expected space, and the query time of our algorithm are O( n(4-3 beta) log n), O(n(4-3 beta)), and O(1/delta(3)n(beta) log n), respectively. The algorithm computes the number of visible segments from p, or mp, exactly if m(p) <= (1)/(3)(delta)n(beta) log ***, it computes a ( 1+ delta)-approximation m'(p) with the probability of at least 1- 1/log n, where m(p) <= m'(p) <= ( 1 + delta) m(p).

关键词： Computational geometry Visibility randomized algorithm Approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

Retrieving Routes of Interest Over Road Networks 17th

Retrieving Routes of Interest Over Road Networks

引用

17th International Conference on Web-Age Information Management (WAIM)

作者： Li, Wengen Cao, Jiannong Guan, Jihong Yiu, Man Lung Zhou, Shuigeng Hong Kong Polytech Univ Hong Kong Hong Kong Peoples R China Tongji Univ Shanghai Peoples R China Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9783319399379;9783319399362

In this paper, we propose route of interest (ROI) query which allows users to specify their interests with query keywords and returns a route such that (i) its distance is less than a distance threshold and (ii) its relevance to the query keywords is maximized. ROI query is particularly helpful for tourists and city explorers. For example, a tourist may wish to find a route from a scenic spot to her hotel to cover many artware shops. It is challenging to efficiently answer ROI query due to its NP-hard complexity. Novelly, we propose an adaptive route sampling framework that adaptively computes a route according to a given response time, and gradually improve the quality of the route with time. Moreover, we design a suite of route sampling techniques under this framework. Experiments on real data suggest that our proposed solution can return high quality routes within a short response time.

关键词： Route of interest Route sampling randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The linear voting model 43

The linear voting model

引用

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Cooper, Colin Rivera, Nicolas Department of Informatics King's College London London United Kingdom

ISBN: (纸本)9783959770132

We study voting models on graphs. In the beginning, the vertices of a given graph have some initial opinion. Over time, the opinions on the vertices change by interactions between graph neighbours. Under suitable conditions the system evolves to a state in which all vertices have the same opinion. In this work, we consider a new model of voting, called the Linear Voting Model. This model can be seen as a generalization of several models of voting, including among others, pull voting and push voting. One advantage of our model is that, even though it is very general, it has a rich structure making the analysis tractable. In particular we are able to solve the basic question about voting, the probability that certain opinion wins the poll, and furthermore, given appropriate conditions, we are able to bound the expected time until some opinion wins. © Colin Cooper and Nicolas Rivera.

关键词： Interacting particles Probabilistic voting randomized algorithm Voter model

来源：评论

学校读者我要写书评

暂无评论

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651

引用

2016年

Mit :: Lcs :: Tr :: Mit-Lcs-Tr-651 by published by

关键词： adversary algorithm chapter execution general model lemma mit-lcs-tr-651 mutual exclusion optimal randomized player probability probability distribution probability space random random variable random variables randomized randomized algorithm randomized algorithms randomized computing set

来源：评论

学校读者我要写书评

暂无评论

randomized oblivious integral routing for minimizing power cost

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part2期607卷 221-246页

作者： Shi, Yangguang Zhang, Fa Wu, Jie Liu, Zhiyong Chinese Acad Sci Inst Comp Technol Beijing Key Lab Mobile Comp & Pervas Device Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Chinese Acad Sci Inst Comp Technol Key Lab Intelligent Informat Proc Beijing Peoples R China Temple Univ Coll Sci & Technol Dept Comp & Informat Sci Philadelphia PA 19122 USA Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing Peoples R China

Given an undirected network G(V, E) and a set of traffic requests R, the minimum power-cost routing problem requires that each R-k is an element of R, be routed along a single path to minimize Sigma(e is an element of E)(l(e))(alpha), where l(e) is the traffic load on edge e and alpha is a constant greater than 1. Typically, alpha is an element of (1,3]. This problem is important in optimizing the energy consumption of networks. To address this problem, we propose a randomized oblivious routing algorithm. An oblivious routing algorithm makes decisions independently of the current traffic in the network. This feature enables the efficient implementation of our algorithm in a distributed manner, which is desirable for large-scale high-capacity networks. An important feature of our work is that our algorithm can satisfy the integral constraint, which requires that each traffic request Rk should follow a single path. We prove that, given this constraint, no randomized oblivious routing algorithm can guarantee a competitive ratio bounded by o(vertical bar E vertical bar(alpha-1/alpha+1)). By contrast, our approach provides a competitive ratio of O(vertical bar E vertical bar(alpha-1/alpha+1) log(2 alpha/alpha+1) vertical bar V vertical bar . log(alpha-1) D), where D is the maximum demand of traffic requests. Furthermore, our results also hold for a more general case where the objective is to minimize Sigma(e)(l(e))(p), where p >= I is an arbitrary unknown parameter with a given upper bound alpha >1. The theoretical results established in proving these bounds can be further generalized to a framework of designing and analyzing oblivious integral routing algorithms, which is significant for research on minimizing Sigma(e)(l(e))(alpha) in specific scenarios with simplified problem settings. For instance, we prove that this framework can generate an oblivious integral routing algorithm whose competitive ratio can be bounded by O(log(alpha) vertical bar V vertical bar . log(a

关键词： Oblivious routing Integral routing randomized algorithm Competitive ratio Energy efficiency

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient randomized Switching for Maximizing Lifetime in Tree-Based Wireless Sensor Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2015年第5期23卷 1401-1415页

作者： Imon, Sk Kajal Arefin Khan, Adnan Di Francesco, Mario Das, Sajal K. Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA Aalto Univ Dept Comp Sci & Engn Aalto 00076 Finland Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA

In most wireless sensor network (WSN) applications, data are typically gathered by sensor nodes and reported to a data collection point called sink. To support such a data collection pattern, a tree structure rooted at the sink is defined. Depending on various factors, including the WSN topology and the availability of resources, the energy consumption of nodes in different paths of the data collection tree may vary largely, thus affecting the overall network lifetime. This paper addresses the problem of lifetime maximization of WSNs based on data collection trees. Specifically, we propose a novel and efficient algorithm, called randomized Switching for Maximizing Lifetime (RaSMaLai), that aims at extending the lifetime of WSNs through load balancing. Given an initial data collection tree, RaSMaLai randomly switches some sensor nodes from their original paths to other paths with lower load. We prove that, under appropriate settings of the operating parameters, RaSMaLai converges with a low time complexity. We further design a distributed version of our algorithm. Through an extensive performance evaluation study that includes simulation of large-scale scenarios and real experiments on a WSN testbed, we show that the proposed RaSMaLai algorithm and its distributed version achieve a longer network lifetime than the state-of-the-art solutions.

关键词： Data collection tree load balancing network lifetime randomized algorithm wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

randomized algorithm for global optimization with bounded memory

引用

MATHEMATICS AND COMPUTERS IN SIMULATION 2010年第6期80卷 1068-1081页

作者： Calvin, James M. New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We describe a class of adaptive algorithms tor approximating the global minimum of a function defined on a compact subset of R(d) The algorithms are adaptive versions of Monte Carlo search and use a memory of a fixed number of past observations By choosing a large enough memory. the convergence rate can be made to exceed any power of the convergence rate obtained with standard Monte Carlo search (C) 2008 IMACS Published by Elsevier B V All rights reserved

关键词： Global optimization Monte Carlo methods Parallel algorithm Point process randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized parameterized algorithms for P₂-Packing and Co-Path Packing problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期29卷 125-140页

作者： Feng, Qilong Wang, Jianxin Li, Shaohua Chen, Jianer Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

In this paper, we study the Parameterized P-2-Packing problem and Parameterized Co-Path Packing problem from random perspective. For the Parameterized P-2-Packing problem, based on the structure analysis of the problem and using random partition technique, a randomized parameterized algorithm of running time O*(6.75(k)) is obtained, improving the current best result O*(8(k)). For the Parameterized Co-Path Packing problem, we firstly study the kernel and randomized algorithm for the degree-bounded instance, where each vertex in the instance has degree at most three. A kernel of size 20k and a randomized algorithm of running time O*(2(k)) are given for the Parameterized Co-Path Packing problem with bounded degree constraint. By applying iterative compression technique and based on the randomized algorithm for degree bounded problem, a randomized algorithm of running time O*(3(k)) is given for the Parameterized Co-Path Packing problem.

关键词： P-2-Packing Co-Path Packing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：