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

第24届中国控制与决策会议

作者： Mikhail Morozkov Oleg Granichin Zeev Volkovich Department of Mathematics and Mechanics Saint Petersburg State University

One of the most difficult problems in cluster analysis is the identification of the number of groups in a given data set. In this paper we offer the randomized approach in the rate distortion framework. A randomized algorithm has been suggested to allocate this position. The scenario approach is used to significantly reduce the computational complexity. With ability to determine the true number of clusters and perform clustering in real-time operational mode we outline several applications in control systems and decision-making problems that can benefit from algorithm in question essentially. We also provide simulation results to show considerable speed optimization with guaranteed level of probability.

关键词： Clustering randomized algorithms Adaptive Control Optimitzaion

来源：评论

学校读者我要写书评

暂无评论

A Cognitive-inspired Model for Self-organizing Networks

A Cognitive-inspired Model for Self-organizing Networks

引用

IEEE International Conference on Self-Adaptive and Self-Organizing Systems Workshops

作者： Daniel Borkmann Andrea Guazzini Emanuele Massaro Stefan Rudolph Communication Systems Group ETH Zurich Switzerland Institute for Informatics and Telematics National Research Council Pisa Italy Department of Informatics and Systems University of Florence Italy Organic Computing Group University of Augsburg Germany

ISBN: (纸本)9781467351539

In this work we propose a computational scheme inspired by the workings of human cognition. We embed some fundamental aspects of the human cognitive system into this scheme in order to obtain a minimization of computational resources and the evolution of a dynamic knowledge network over time, and apply it to computer networks. Such algorithm is capable of generating suitable strategies to explore huge graphs like the Internet that are too large and too dynamic to be ever perfectly known. The developed algorithm equips each node with a local information about possible hubs which are present in its environment. Such information can be used by a node to change its connections whenever its fitness is not satisfying some given requirements. Eventually, we compare our algorithm with a randomized approach within an ecological scenario for the ICT domain, where a network of nodes carries a certain set of objects, and each node retrieves a subset at a certain time, constrained with limited resources in terms of energy and bandwidth. We show that a cognitive-inspired approach improves the overall networks topology better than a randomized algorithm.

关键词： complex networks cognitive modelling selfawareness systems complex networks Line of nodes Cognitive Maps Self-organizing networks randomized algorithms computational scheme computer network local information. Network

来源：评论

学校读者我要写书评

暂无评论

A random coordinate descent method for large-scale resource allocation problems

A random coordinate descent method for large-scale resource ...

引用

IEEE Annual Conference on Decision and Control

作者： I. Necoara University Politehnica Bucharest Automatic Control and Systems Engineering Department

ISBN: (纸本)9781467320658

In this paper we develop a randomized (block) coordinate descent method for solving singly linear equality constrained optimization problems that appear for example in resource allocation over networks. We show that for strongly convex objective functions the new algorithm has an expected linear convergence rate that depends on the second smallest eigenvalue λ_2(Q) of a matrix Q that is defined in terms of the probabilities and the number of blocks. However, the computational complexity per iteration of our method is much simpler than of a method based on full gradient information. We also focus on how to choose the probabilities to make this randomized algorithm to converge as fast as possible and we arrive at solving a sparse SDP. Finally, we present some numerical results for our method that show its efficiency on huge sparse problems.

关键词： descent method Resource utilization management of resources randomized algorithms Coordinates iterative methods Converge

来源：评论

学校读者我要写书评

暂无评论

The Effectiveness of Lloyd-Type Methods for the k-Means Problem

引用

JOURNAL OF THE ACM 2012年第6期59卷 28-28页

作者： Ostrovsky, Rafail Rabani, Yuval Schulman, Leonard J. Swamy, Chaitanya Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Hebrew Univ Jerusalem Rachel & Selim Benin Sch Comp Sci & Engn IL-91904 Jerusalem Israel Hebrew Univ Jerusalem Ctr Excellence Algorithms IL-91904 Jerusalem Israel CALTECH Pasadena CA 91125 USA Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration.

关键词： algorithms Theory randomized algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Decoding by Sampling: A randomized Lattice Algorithm for Bounded Distance Decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第9期57卷 5933-5945页

作者： Liu, Shuiyin Ling, Cong Stehle, Damien Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn London SW7 2AZ England U Lyon CNRS Lab LIP ENS LyonINRIAUCBL F-69364 Lyon 07 France

Despite its reduced complexity, lattice reduction-aided decoding exhibits a widening gap to maximum-likelihood (ML) performance as the dimension increases. To improve its performance, this paper presents randomized lattice decoding based on Klein's sampling technique, which is a randomized version of Babai's nearest plane algorithm [i.e., successive interference cancelation (SIC)] and samples lattice points from a Gaussian-like distribution over the lattice. To find the closest lattice point, Klein's algorithm is used to sample some lattice points and the closest among those samples is chosen. Lattice reduction increases the probability of finding the closest lattice point, and only needs to be run once during preprocessing. Further, the sampling can operate very efficiently in parallel. The technical contribution of this paper is twofold: we analyze and optimize the decoding radius of sampling decoding resulting in better error performance than Klein's original algorithm, and propose a very efficient implementation of random rounding. Of particular interest is that a fixed gain in the decoding radius compared to Babai's decoding can be achieved at polynomial complexity. The proposed decoder is useful for moderate dimensions where sphere decoding becomes computationally intensive, while lattice reduction-aided decoding starts to suffer considerable loss. Simulation results demonstrate near-ML performance is achieved by a moderate number of samples, even if the dimension is as high as 32.

关键词： Bounded distance decoding lattice decoding lattice reduction randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Teaching randomized learners with feedback

引用

INFORMATION AND COMPUTATION 2011年第3期209卷 296-319页

作者： Balbach, Frank J. Zeugmann, Thomas Hokkaido Univ Div Comp Sci Sapporo Hokkaido 0600814 Japan Pattern Sci AG Freigericht Germany

The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of the learner's memory size and of the presence or absence of feedback. Moreover, in the new model the order in which examples are presented may influence the teaching process. The resulting models are related to Markov decision processes, and characterizations of optimal teachers for memoryless learners with feedback and for learners with infinite memory and feedback are shown. Furthermore, in the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching with inconsistent teachers. Characterization theorems for teachability from positive data for both ordinary teachers and inconsistent teachers with and without feedback are provided. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Algorithmic teaching randomized algorithms Computational complexity

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for minimum distance localization

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2007年第9期26卷 917-933页

作者： Rao, Malvika Dudek, Gregory Whitesides, Sue McGill Univ Dept Comp Sci Montreal PQ H3A 2A7 Canada

The problem of minimum distance localization in environments that may contain self-similarities is addressed. A mobile robot is placed at an unknown location inside a 2D self-similar polygonal environment P. The robot has a map of P and can compute visibility data through sensing. However the self-similarities in the environment mean that the same visibility data may correspond to several different locations. The goal, therefore, is to determine the robot's true initial location while minimizing the distance traveled by the robot. Two randomized approximation algorithms are presented that solve minimum distance localization. The performance of the proposed algorithms is evaluated empirically.

关键词： localization sensing optimal path ambiguity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Satisfiability Algorithm for AC~0 12

A Satisfiability Algorithm for AC~0

引用

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

作者： Russell Impagliazzo William Matthews Ramamohan Paturi Department of Computer Science and Engineering University of California

ISBN: (纸本)9781611972108

We consider the problem of efficiently enumerating the satisfying assignments to AC~0 circuits. We give a zero-error randomized algorithm which takes an AC~0 circuit as input and constructs a set of restrictions which partitions {0, 1}~n so that under each restriction the value of the circuit is constant. Let d denote the depth of the circuit and cn denote the number of gates. This algorithm runs in time |C|2~(n(1-μc, d)) where |C| is the size of the circuit for μ_(c, d) ≥ 1/O[lg c ＋ d lg d]~(d-1) with probability at least 1 - 2~(-n). As a result, we get improved exponential time algorithms for AC~0 circuit satisfiability and for counting solutions. In addition, we get an improved bound on the correlation of AC~0 circuits with parity.

关键词： computability algorithms cyanogen Denote zero-error Restriction Electric circuits randomized algorithms Exponential time

来源：评论

学校读者我要写书评

暂无评论

randomized OBDDs for the most significant bit of multiplication need exponential space

引用

INFORMATION PROCESSING LETTERS 2011年第4期111卷 151-155页

作者： Bollig, Beate Gille, Marc TU Dortmund Informat LS2 D-44221 Dortmund Germany

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Only in 2008 the question whether the deterministic OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. Since probabilistic methods have turned out to be useful in almost all areas of computer science, one may ask whether randomization can help to represent the most significant bit of integer multiplication in smaller size. Here, it is proved that the randomized OBDD complexity is also exponential. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Computational complexity randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：