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

A counterexample to rapid mixing of the Ge-Stefankovic process

ELECTRONIC COMMUNICATIONS IN PROBABILITY 2012年第none期17卷 1-6页

作者： Goldberg, Leslie Ann Jerrum, Mark Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ London Sch Math Sci London E1 NS England

Ge and Stefankovic have recently introduced a Markov chain which, if rapidly mixing, would provide an efficient procedure for sampling independent sets in a bipartite graph. Such a procedure would be a breakthrough because it would give an efficient randomised algorithm for approximately counting independent sets in a bipartite graph, which would in turn imply the existence of efficient approximation algorithms for a number of significant counting problems whose computational complexity is so far unresolved. Their Markov chain is based on a novel two-variable graph polynomial which, when specialised to a bipartite graph, and evaluated at the point (1/2, 1), gives the number of independent sets in the graph. The Markov chain is promising, in the sense that it overcomes the most obvious barrier to rapid mixing. However, we show here, by exhibiting a sequence of counterexamples, that its mixing time is exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.

关键词： Glauber dynamics Independent sets in graphs Markov chains Mixing time randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Smallest eigenvalue distributions for two classes of β-Jacobi ensembles

引用

JOURNAL OF MATHEMATICAL PHYSICS 2012年第10期53卷 103301-103301-15页

作者： Dumitriu, Ioana Univ Washington Dept Math Seattle WA 98195 USA

We compute the exact and limiting smallest eigenvalue distributions for two classes of beta-Jacobi ensembles not covered by previous studies. In the general beta case, these distributions are given by multivariate hypergeometric F-2(1)2/beta functions, whose behavior can be analyzed asymptotically for special values of beta which include beta is an element of 2N(+) as well as for beta = 1. Interest in these objects stems from their connections (in the beta = 1, 2 cases) to principal submatrices of Haar-distributed (orthogonal, unitary) matrices appearing in randomized, communication-optimal, fast, and stable algorithms for eigenvalue computations [J. Demmel, I. Dumitriu, and O. Holtz, "Fast linear algebra is stable," Numer. Math. 108, 59-91 (2007);G. Ballard, J. Demmel, and I. Dumitriu, "Minimizing communication for eigenproblems and the singular value decomposition," 2010. Preprint]. (C) 2012 American Institute of Physics. [http://***/10.1063/1.4748969]

关键词： eigenvalues and eigenfunctions Jacobian matrices randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

WILD BINARY SEGMENTATION FOR MULTIPLE CHANGE-POINT DETECTION

引用

ANNALS OF STATISTICS 2014年第6期42卷 2243-2281页

作者： Fryzlewicz, Piotr London Sch Econ Dept Stat London WC2A 2AE England

We propose a new technique, called wild binary segmentation (WBS), for consistent estimation of the number and locations of multiple change-points in data. We assume that the number of change-points can increase to infinity with the sample size. Due to a certain random localisation mechanism, WBS works even for very short spacings between the change-points and/or very small jump magnitudes, unlike standard binary segmentation. On the other hand, despite its use of localisation, WBS does not require the choice of a window or span parameter, and does not lead to a significant increase in computational complexity. WBS is also easy to code. We propose two stopping criteria for WBS: one based on thresholding and the other based on what we term the 'strengthened Schwarz information criterion'. We provide default recommended values of the parameters of the procedure and show that it offers very good practical performance in comparison with the state of the art. The 'WBS methodology is implemented in the R package wbs, available on CRAN. In addition, we provide a new proof of consistency of binary segmentation with improved rates of convergence, as well as a corresponding result for WBS.

关键词： Multiple change-points change-point detection binary segmentation randomised algorithms thresholding Bayesian information criterion

来源：评论

学校读者我要写书评

暂无评论

Sampling Eulerian orientations of triangular lattice graphs

引用

JOURNAL OF DISCRETE algorithms 2009年第2期7卷 168-180页

作者： Creed, Paidi Univ Edinburgh Sch Informat Edinburgh EH9 3JZ Midlothian Scotland

We consider the problem of sampling from the uniform distribution on the set of Eulerian orientations of subgraphs of the triangular lattice. Although Mihail and Winkler (1989) showed that this can be achieved in polynomial time for any graph, the algorithm studied here is more natural in the context of planar Eulerian graphs. We analyse the mixing time of a Markov chain on the Eulerian orientations of a planar graph which moves between orientations by reversing the edges of directed faces. Using path coupling and the comparison method we obtain a polynomial upper bound on the mixing time of this chain for any solid subgraph of the triangular lattice. By considering the conductance of the chain we show that there exist non-solid subgraphs (subgraphs with holes) for which the chain will always take an exponential amount of time to converge. Finally, we show that the problem of counting Eulerian orientations remains #P-complete when restricted to planar graphs (Mihail and Winkler had already established this for general graphs). (C) 2008 Elsevier B.V. All rights reserved.

关键词： randomised algorithms Markov chain Monte Carlo Rapid mixing Torpid mixing Eulerian orientations

来源：评论

学校读者我要写书评

暂无评论

Product replacement in the monster

引用

EXPERIMENTAL MATHEMATICS 2003年第1期12卷 123-126页

作者： Holmes, PE Linton, SA Murray, SH Univ Birmingham Sch Math & Stat Birmingham B15 2TT W Midlands England Univ St Andrews Sch Comp Sci St Andrews KY16 9SS Fife Scotland

We show that the product replacement algorithm can be used to produce random elements of the Monster group. These random elements are shown to have the same distribution of element orders as uniformly distributed rand... 详细信息

关键词： monster group randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration

引用

JOURNAL OF COMPLEXITY 2023年第1期79卷

作者： Kuo, Frances Y. Nuyens, Dirk Wilkes, Laurence UNSW Sydney Sydney Australia Katholieke Univ Leuven Leuven Belgium

We show that a very simple randomised algorithm for numerical integration can produce a near optimal rate of convergence for integrals of functions in the d-dimensional weighted Korobov space. This algorithm uses a lattice rule with a fixed generating vector and the only random element is the choice of the number of function evaluations. For a given computational budget n of a maximum allowed number of function evaluations, we uniformly pick a prime p in the range n/2 < p <= n. We show error bounds for the randomised error, which is defined as the worst case expected error, of the form O (n(-alpha-1/2+delta)), with delta > 0, for a Korobov space with smoothness alpha > 1/2 and general weights. The implied constant in the bound is dimension-independent given the usual conditions on the weights. We present an algorithm that can construct suitable generating vectors offline ahead of time at cost O (dn(4)/ lnn) when the weight parameters defining the Korobov spaces are so-called product weights. For this case, numerical experiments confirm our theory that the new randomised algorithm achieves the near optimal rate of the randomised error.(c) 2023 Elsevier Inc. All rights reserved.

关键词： randomised algorithms Numerical integration Lattice rules Tractability Quasi-Monte Carlo Korobov space

来源：评论

学校读者我要写书评

暂无评论

THE DEPRIORITISED APPROACH TO PRIORITISED algorithms

引用

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY 2009年第3期79卷 523-524页

作者： Howe, Stephen Australian Natl Univ Inst Math Sci Ctr Math & Applicat Canberra ACT 0200 Australia

The article focuses on the average case analyses of heuristics for graph optimisation problems and considers algorithms on dominating sets of random regular directed graphs. Results of these analyses find new upper bounds on domination numbers of these graphs. The graphs' algorithms are known as prioritised algorithms. The extension of the deprioritised approach to a larger class of prioritised algorithms is stated as the contribution of the thesis. Furthermore, the thesis shows the new theory by applying it to two algorithms.

关键词： randomised algorithms deprioritised algorithms random regular digaphs dominating sets

来源：评论

学校读者我要写书评

暂无评论

Using Random Butterfly Transformations in Parallel Schur Complement-Based Preconditioning

Using Random Butterfly Transformations in Parallel Schur Com...

引用

3rd International Conference on Innovative Network Systems and Applications (iNetSApp) held in conjunction with Federated Conference on Computer Science and Information Systems (FedCSIS)

作者： Baboulin, Marc Jamal, Aygul Sosonkina, Masha Univ Paris 11 Bat 425 F-91405 Orsay France Old Dominion Univ Norfolk VA 23529 USA

ISBN: (纸本)9788360810668

We propose to use a randomization technique based on Random Butterfly Transformations (RBT) in the Algebraic Recursive Multilevel Solver (ARMS) to improve the preconditioning phase in the iterative solution of sparse linear systems. We integrated the RBT technique into the parallel version of ARMS (pARMS). The preliminary experimental results on some matrices from the Davis' collection show an improvement of the convergence and accuracy of the results when compared with existing implementations of the pARMS preconditioner.

关键词： iterative methods matrix algebra parallel algorithms randomised algorithms recursive estimation RBT technique algebraic recursive multilevel solver iterative solution matrices pARMS preconditioner parallel ARMS parallel Schur complement-based preconditioning preconditioning phase improvement random butterfly transformations randomization technique sparse linear systems Accuracy Iterative methods Linear systems Program processors Sparse matrices Symmetric matrices Yttrium iterative methods Linear system iterative solution Program processors Symmetric matrix recursive estimation Sparse matrix matrix algebra Parallel algorithms Rare earths yttrium matrices randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Weighted alpha-rate dominating sets in social networks 10

Weighted alpha-rate dominating sets in social networks

引用

International Conference on Signal-Image Technology and Internet-Based Systems SITIS

作者： Greetham, Danica Vukadinovic Poghosyan, Anush Charlton, Nathaniel Univ Reading Dept Math & Stat Ctr Math Human Behav Reading RG6 2AH Berks England CountingLab Ltd Reading Berks England

ISBN: (纸本)9781479979783

We are looking into variants of a domination set problem in social networks. While randomised algorithms for solving the minimum weighted domination set problem and the minimum alpha and alpha-rate domination problem on simple graphs are already present in the literature, we propose here a randomised algorithm for the minimum weighted alpha-rate domination set problem which is, to the best of our knowledge, the first such algorithm. A theoretical approximation bound based on a simple randomised rounding technique is given. The algorithm is implemented in Python and applied to a UK Twitter mentions networks using a measure of individuals' influence (klout) as weights. We argue that the weights of vertices could be interpreted as the costs of getting those individuals on board for a campaign or a behaviour change intervention. The minimum weighted alpha-rate dominating set problem can therefore be seen as finding a set that minimises the total cost and each individual in a network has at least alpha percentage of its neighbours in the chosen set. We also test our algorithm on generated graphs with several thousand vertices and edges. Our results on this real-life Twitter networks and generated graphs show that the implementation is reasonably efficient and thus can be used for real-life applications when creating social network based interventions, designing social media campaigns and potentially improving users' social media experience.

关键词： alpha-rate dominating sets randomised algorithms social networks weighted domination Social Networks randomized algorithms Authoritarianism Social Capital Social Media Pythonidae Set (Psychology)

来源：评论

学校读者我要写书评

暂无评论

The Constrained Ski-Rental Problem and its Application to Online Cloud Cost Optimization

The Constrained Ski-Rental Problem and its Application to On...

引用

32nd IEEE INFOCOM Conference

作者： Khanafer, Ali Kodialam, Murali Puttaswamy, Krishna P. N. Univ Illinois Coordinated Sci Lab 1101 W Springfield Ave Urbana IL 61801 USA Bell Labs Alcatel Lucent Murray Hill NJ 07974 USA

ISBN: (纸本)9781467359467

Cloud service providers (CSPs) enable tenants to elastically scale their resources to meet their demands. In fact, there are various types of resources offered at various price points. While running applications on the cloud, a tenant aiming to minimize cost is often faced with crucial trade-off considerations. For instance, upon each arrival of a query, a web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response so as to reduce the compute costs of future requests. The Ski-Rental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy trade-off;in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In this paper, we introduce a variant of the classical Ski-Rental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio (CR) performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Further, we apply our solution to a cloud file system and demonstrate the cost savings obtained in comparison to other competing schemes. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

关键词： cloud computing cost reduction deterministic algorithms optimisation pricing randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：