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

Shortest Cycle Through Specified Elements 12

学校读者我要写书评

暂无评论

Shortest Cycle Through Specified Elements

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Andreas Bjoerklund Thore Husfeldt Nina Taslaman Lund University Lund University Sweden and IT University of Copenhagen IT University of Copenhagen

We give a randomized algorithm that finds a shortest simple cycle through a given set of k vertices or edges in an n-vertex undirected graph in time 2~kn~(O(1)).

ISBN: (纸本)9781611972108

We give a randomized algorithm that finds a shortest simple cycle through a given set of k vertices or edges in an n-vertex undirected graph in time 2~kn~(O(1)).

关键词： randomized algorithms Simple Cycle undirected graph vertex head

An experimental study of a simple, distributed edge-coloring algorithm

学校读者我要写书评

暂无评论

ACM Journal of Experimental Algorithmics 2004年 9卷 1.3–es页

作者： Marathe, Madhav V. Panconesi, Alessandro Risinger, Larry D. Basic and Applied Simulation Science (CCS-5) MS M997 Los Alamos National Laboratory P.O. Box 1663 Los Alamos 87545 NM United States Dipartimento di Informatica Universitá La Sapienza di Roma via Salaria 113 Roma 00198 Italy ISR5 Los Alamos National Laboratory MS J570 P.O. Box 1663 Los Alamos 87545 NM United States

We conduct an experimental analysis of a distributed randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [Grable and Panconesi 1997]. We test the algorithm on a number of random as well as nonrandom graph families. The test cases were chosen based on two objectives: (i) to provide insights into the worst-case behavior (in terms of time and quality) of the algorithm and (ii) to test the performance of the algorithm with instances that are likely to arise in practice. Our main results include the following: (1) The empirical results obtained compare very well with the recent empirical results reported by other researchers [Durand et al. 1994, 1998;Jain and Werth 1995]. (2) The empirical results confirm the bounds on the running time and the solution quality as claimed in the theoretical paper. Our results show that for certain classes of graphs the algorithm is likely to perform much better than the analysis suggests. (3) The results demonstrate that the algorithm might be well suited (from a theoretical as well as practical standpoint) for edge coloring graphs quickly and efficiently in a distributed setting. Based on our empirical study, we propose a simple modification of the original algorithm with substantially improved performance in practice. © 2004 ACM.

关键词： Distributed algorithms Edge coloring Experimental analysis of algorithms High performance computing randomized algorithms Scheduling

Adaptive randomized dimension reduction on massive data

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2017年第1期18卷

作者： Gregory Darnell Stoyan Georgiev Sayan Mukherjee Barbara E. Engelhardt Lewis-Sigler Institute Princeton University Princeton NJ Google Palo Alto CA Departments of Statistical Science Mathematics and Computer Science Duke University Durham NC Department of Computer Science Center for Statistics and Machine Learning Princeton University Princeton NJ

The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduction methods. In this paper, we develop an approach for dimension reduction that exploits the assumption of low rank structure in high dimensional data to gain both computational and statistical advantages. We adapt recent randomized low-rank approximation algorithms to provide an efficient solution to principal component analysis (PCA), and we use this efficient solver to improve estimation in large-scale linear mixed models (LMM) for association mapping in statistical genomics. A key observation in this paper is that randomization serves a dual role, improving both computational and statistical performance by implicitly regularizing the covariance matrix estimate of the random effect in an LMM. These statistical and computational advantages are highlighted in our experiments on simulated data and large-scale genomic studies.

关键词： Krylov subspace methods dimension reduction generalized eigendecompositon genomics linear mixed models low-rank random projections randomized algorithms supervised

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

学校读者我要写书评

暂无评论

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

IEEE INFOCOM

作者： Ali Khanafer Murali Kodialam Krishna P. N. Puttaswamy Coordinated Science Laboratory University of Illinois at Urbana-Champaign USA Bell Laboratories Alcatel-Lucent Murray Hill NJ USA

ISBN: (纸本)9781467359443

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.

关键词： tenants Property Leasing Remuneration Wages cost analysis cache storage skier moment distribution Skiing File systems randomized algorithms second moment central processing units Scheme tradeoffs

Quasirandom rumor spreading: An experimental analysis

学校读者我要写书评

暂无评论

ACM Journal of Experimental Algorithmics 2008年第PP3.1–3.13期16卷 3.1–3.13页

作者： Benjamin Doerr Tobias Friedrich Marvin Künnemann Thomas Sauerwald Max-Planck-Institut für Informatik Germany Universität des Saarlandes Germany

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round, each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the *** for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical *** this work, we compare the two models experimentally. Not only does this show that the quasirandom model generally is faster, but it also shows that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom *** advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.

关键词： Rumor spreading experimental analysis randomized algorithms

Distributed matrix completion and robust factorization

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2015年第1期16卷

作者： Lester Mackey Ameet Talwalkar Michael I. Jordan Department of Statistics Stanford University Stanford CA Computer Science Department University of California Los Angeles Los Angeles CA Department of Electrical Engineering and Computer Science and Department of Statistics University of California Berkeley Berkeley CA

If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.

关键词： collaborative filtering divide-and-conquer matrix completion matrix factorization parallel and distributed algorithms randomized algorithms robust matrix factorization video surveillance

Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2013年第1期14卷

作者： Kevin Murphy Bernhard Schölkopf Shusen Wang Zhihua Zhang Google MPI for Intelligent Systems College of Computer Science and Technology Zhejiang University Hangzhou Zhejiang China Department of Computer Science and Engineering Shanghai Jiao Tong University Shanghai China

The CUR matrix decomposition and the Nyström approximation are two important low-rank matrix approximation techniques. The Nyström method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nyström *** this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nyström algorithms with expected relative-error bounds. The proposed CUR and Nyström algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nyström method and the ensemble Nyström method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.

关键词： CUR matrix decomposition adaptive sampling large-scale matrix computation randomized algorithms the Nyström method

Revisiting the Nyström method for improved large-scale machine learning

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2016年第1期17卷

作者： Kevin Murphy Bernhard Schölkopf Alex Gittens Michael W. Mahoney Google MPI for Intelligent Systems International Computer Science Institute and Department of Statistics University of California Berkeley Berkeley CA

We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods; they characterize the effects of common data preprocessing steps on the performance of these algorithms; and they point to important differences between uniform sampling and nonuniform sampling methods based on leverage scores. In addition, our empirical results illustrate that existing theory is so weak that it does not provide even a qualitative guide to practice. Thus, we complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds--e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error--and they point to future directions to make these algorithms useful in even larger-scale machine learning applications.

关键词： Nyström approximation kernel methods low-rank approximation numerical linear algebra randomized algorithms

Stochastic primal-dual coordinate method for regularized empirical risk minimization

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research 2017年第1期18卷

作者： Yuchen Zhang Lin Xiao Department of Computer Science Stanford University Stanford CA Microsoft Research Redmond WA

We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variables. An extrapolation step on the primal variables is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.

关键词： computational complexity convex-concave saddle empirical risk minimization point problems primal-dual algorithms randomized algorithms