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

On a simple randomized algorithm for finding a 2-factor in sparse graphs

INFORMATION PROCESSING LETTERS 2005年第1期95卷 321-327页

作者： Pandurangan, G Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We analyze the performance of a simple randomized algorithm for finding 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of degree at most three. For the directed case, the algorithm finds a 2-factor in O(n(2)) expected time. The analysis of our algorithm is based on random walks on the line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [On selecting a satisfying truth assignment, in: Proc. 32nd Annual IEEE Symp. on the Foundations of Computer Science (FOCS), 1991, p. 163]. For the undirected case, the algorithm finds a 2-factor in O(n(3)) expected time. We also analyze random versions of these graphs and show that cycles of length Q (n/log n) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [Finding hidden Hamilton cycles, Random Structures algorithms 5 (1994) 395] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [On approximating the longest path in a graph, Algorithmica 18 (1997) 82]. (c) 2005 Elsevier B.V. All rights reserved.

关键词： graph algorithms randomized algorithms random walks sparse graphs 2-factor Hamiltonian cycle long cycle

来源：评论

学校读者我要写书评

暂无评论

randomized Sensor Selection for Nonlinear Systems With Application to Target Localization

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2019年第4期4卷 3553-3560页

作者： Bopardikar, Shaunak D. Ennasr, Osatna Tan, Xiaobo Michigan State Univ Elect & Comp Engn Dept E Lansing MI 48824 USA

Given a nonlinear dynamical system, this letter considers the problem of selecting a subset of the total set of sensors that has provable guarantees on standard metrics related to the nonlinear observability Gramian. The key contribution is a simple randomized algorithm that samples the sensors uniformly without replacement, and yields probabilistic guarantees on the minimum eigenvalue or the inverse of the condition number of the nonlinear observability Gramian relative to that of the complete set of sensors. Numerical studies reveal that the utility of the theoretical results lies in the regime of large total number of sensors wherein the combinatorial nature of the problem presents a significant computational challenge. The results are demonstrated numerically on a problem of moving target localization using an extended Kalman filter in two scenarios: one using range sensors and another with time-difference-of-arrival measurements. A graceful degradation of performance with a decreased number of sensors is observed when compared to the use of all of the sensors for localization. It is also observed that for certain metrics, the proposed approach provides an improvement over a heuristic that selects the sensors in a greedy manner based on the contribution of an additional sensor toward the observability Gramian metric.

关键词： Localization probability and statistical methods sensor networks randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A distributed randomized method for the identification of switched ARX systems

引用

INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING 2024年第5期38卷 1621-1635页

作者： Yu, Miao Bianchi, Federico Piroddi, Luigi Politecn Milan Dipartimento Elettr Informaz & Bioingn Milan Italy Politecn Milan Dipartimento Elettr Informaz & Bioingn I-20133 Milan Italy

The identification of switched systems amounts to a mixed integer nonlinear optimization problem, where the continuous variables are associated to the model parameterizations of the different modes, and the discrete ones are related to the switching signal (each data sample is assigned to a mode, and switching occurs when the mode assignment changes over time). In the batch form of the identification problem, the combinatorial complexity increases exponentially with the size of the training set, which makes the precise identification of the switching signal the most challenging task in the identification problem. To tackle this complexity we propose a distributed optimization approach, based on the solution of multiple instances of a much simpler problem, where switching can occur only at specific time instants (different for each subproblem), and an information sharing mechanism that preserves likely switching times to improve the local solutions. We employ an adapted version of a previously developed randomized algorithm to solve the individual subproblems. Another important feature of the proposed method is an a posteriori heuristic correction method, that is applied to further refine the switching locations based on the estimated local models before the information sharing phase. The performance of the proposed algorithm is analyzed and compared with other methods on synthetic datasets.

关键词： distributed optimization identification randomized algorithms switched systems identification

来源：评论

学校读者我要写书评

暂无评论

An improved randomized approximation algorithm for maximum triangle packing

引用

DISCRETE APPLIED MATHEMATICS 2009年第7期157卷 1640-1646页

作者： Chen, Zhi-Zhong Tanahashi, Ruka Wang, Lusheng Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of 83/43 (1 - is an element of)(approximate to 0.518(1 - is an element of)) for any constant is an element of > 0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1 - is an element of) for any constant E > 0. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximum triangle packing Approximation algorithms randomized algorithms Maximum-weight b-matching

来源：评论

学校读者我要写书评

暂无评论

randomized SUBSPACE ITERATION: ANALYSIS OF CANONICAL ANGLES AND UNITARILY INVARIANT NORMS

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2019年第1期40卷 23-48页

作者： Saibaba, Arvind K. North Carolina State Univ Dept Math Raleigh NC 27695 USA

This paper analyzes the randomized subspace iteration for the computation of low-rank approximations. We present three different kinds of bounds. First, we derive both bounds for the canonical angles between the exact and the approximate singular subspaces. Second, we derive bounds for the low-rank approximation in any unitarily invariant norm (including the Schatten-p norm). This generalizes the bounds for spectral and Frobenius norms found in the literature. Third, we present bounds for the accuracy of the singular values. The bounds are structural in that they are applicable to any starting guess, be it random or deterministic, that satisfies some minimal assumptions. Specialized bounds are provided when a Gaussian random matrix is used as the starting guess. Numerical experiments demonstrate the effectiveness of the proposed bounds.

关键词： singular value decomposition randomized algorithms canonical angles low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

A sequentially optimal randomized algorithm for robust feasibility problems

引用

REVISTA IBEROAMERICANA DE AUTOMATICA E INFORMATICA INDUSTRIAL 2013年第1期10卷 50-61页

作者： Alamo, T. Tempo, R. Ramirez, D. R. Luque, A. Camacho, E. F. Univ Seville Escuela Tecn Super Ingn Dpto Ingn Sistemas & Automat Seville 41092 Spain Politecn Torino IEIIT CNR I-10129 Turin Italy

This paper proposes a randomized algorithm for feasibility of uncertain LMIs. The algorithm is based on the solution of a sequence of semidefinite optimization problems involving a reduced number of constraints. A bound of the maximum number of iterations required by the algorithm is given. Finally, the performance and behaviour of the algorithm are illustrated by means of a numerical example.

关键词： robust feasibility linear matrix inequalities randomized algorithms robust control

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems

引用

PARALLEL COMPUTING 2014年第7期40卷 213-223页

作者： Baboulin, Marc Becker, Dulceneia Bosilca, George Danalis, Anthony Dongarra, Jack Univ Paris 11 Rech Informat Lab Inria F-91405 Orsay France Univ Tennessee Innovat Comp Lab Knoxville TN USA

randomized algorithms are gaining ground in high-performance computing applications as they have the potential to outperform deterministic methods, while still providing accurate results. We propose a randomized solver for distributed multicore architectures to efficiently solve large dense symmetric indefinite linear systems that are encountered, for instance, in parameter estimation problems or electromagnetism simulations. The contribution of this paper is to propose efficient kernels for applying random butterfly transformations and a new distributed implementation combined with a runtime (PaRSEC) that automatically adjusts data structures, data mappings, and the scheduling as systems scale up. Both the parallel distributed solver and the supporting runtime environment are innovative. To our knowledge, the randomization approach associated with this solver has never been used in public domain software for symmetric indefinite systems. The underlying runtime framework allows seamless data mapping and task scheduling, mapping its capabilities to the underlying hardware features of heterogeneous distributed architectures. The performance of our software is similar to that obtained for symmetric positive definite systems, but requires only half the execution time and half the amount of data storage of a general dense solver. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Distributed linear algebra solvers Symmetric indefinite systems LDLT factorization PaRSEC runtime

来源：评论

学校读者我要写书评

暂无评论

A randomized -Competitive Algorithm for the Online Connected Facility Location Problem

引用

ALGORITHMICA 2016年第4期76卷 1139-1157页

作者： San Felice, Mario Cesar Williamson, David P. Lee, Orlando Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is -competitive. Since there is a lower bound of for this problem, our result achieves the best possible competitive ratio, asymptotically.

关键词： Online algorithms Competitive analysis Connected facility location Steiner tree Approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized Linear Algebra Approaches to Estimate the von Neumann Entropy of Density Matrices

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第8期66卷 5003-5021页

作者： Kontopoulou, Eugenia-Maria Dexter, Gregory-Paul Szpankowski, Wojciech Grama, Ananth Drineas, Petros Purdue Univ Dept Comp Sci W Lafayette IN 47906 USA

The von Neumann entropy, named after John von Neumann, is an extension of the classical concept of entropy to the field of quantum mechanics. From a numerical perspective, von Neumann entropy can be computed simply by computing all eigenvalues of a density matrix, an operation that could be prohibitively expensive for large-scale density matrices. We present and analyze three randomized algorithms to approximate von Neumann entropy of real density matrices: our algorithms leverage recent developments in the randomized Numerical Linear Algebra (RandNLA) literature, such as randomized trace estimators, provable bounds for the power method, and the use of random projections to approximate the eigenvalues of a matrix. All three algorithms come with provable accuracy guarantees and our experimental evaluations support our theoretical findings showing considerable speedup with small loss in accuracy.

关键词： Approximation algorithms Entropy Symmetric matrices Eigenvalues and eigenfunctions Linear algebra Quantum mechanics Taylor series von Neumann entropy randomized algorithms randNLA Taylor polynomials Chebyshev polynomials random projections

来源：评论

学校读者我要写书评

暂无评论

The power of standard information for multivariate approximation in the randomized setting

引用

MATHEMATICS OF COMPUTATION 2007年第258期76卷 965-988页

作者： Wasilkowski, G. W. Wozniakowski, H. Univ Kentucky Dept Comp Sci Lexington KY 40506 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Warsaw Univ Inst Appl Math Warsaw Poland

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted L-2-norm. We consider functions with an arbitrarily large number of variables, d, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the nth minimal errors, i.e., of the minimal errors among all algorithms using n function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study ( strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor e is polynomial in epsilon(-1) ( strong tractability), and polynomial in d and epsilon(-1) ( tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying ( strong) tractability for standard information is in general difficult, whereas ( strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of d, we prove that strong tractability is equivalent to

关键词： weighted multivariate approximation randomized algorithms Monte Carlo methods tractability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：