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

Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2

作者： Yoram Bachrach Evangelos Markakis Ariel D. Procaccia Jeffrey S. Rosenschein Amin Saberi Hebrew University Jerusalem Israel Center for Mathematics and Computer Science (CWI) Amsterdam the Netherlands Stanford University Palo Alto CA

ISBN: (纸本)9780981738116

Many multiagent domains where cooperation among agents is crucial to achieving a common goal can be modeled as coalitional games. However, in many of these domains, agents are unequal in their power to affect the outcome of the game. Prior research on weighted voting games has explored power indices, which reflect how much "real power" a voter has. Although primarily used for voting games, these indices can be applied to any simple coalitional game. Computing these indices is known to be computationally hard in various domains, so one must sometimes resort to approximate methods for calculating *** suggest and analyze randomized methods to approximate power indices such as the Banzhaf power index and the Shapley-Shubik power index. Our approximation algorithms do not depend on a specific representation of the game, so they can be used in any simple coalitional game. Our methods are based on testing the game's value for several sample coalitions. We also show that no approximation algorithm can do much better for general coalitional games, by providing lower bounds for both deterministic and randomized algorithms for calculating power indices.

关键词： randomized algorithms power indices

来源：评论

学校读者我要写书评

暂无评论

Testing Euclidean Minimum Spanning Trees in the Plane

引用

ACM TRANSACTIONS ON algorithms 2008年第3期4卷 31-31页

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat Coventry CV4 7AL W Midlands England Univ Bonn Dept Comp Sci D-53117 Bonn Germany

Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than epsilon n edges. We assume that G is given in adjacency list representation and the point/vertex set P is given in an array. We present a property testing algorithm that accepts graph G if it is an EMST of P and that rejects with probability at least 2/3 if G differs from every EMST of P in more than epsilon n edges. Our algorithm runs in O(root n/epsilon . log(2)(n/epsilon)) time and has a query complexity of O(root n/epsilon . log(n/epsilon)).

关键词： Euclidean minimum spanning tree property testing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tractability of Multivariate Problems

引用

2008年

作者： Erich Novak Henryk Woźniakowski

ISBN: (数字)9783037195260

ISBN: (纸本)9783037190265

Multivariate problems occur in many applications. These problems are defined on spaces of d-variate functions and d can be huge – in the hundreds or even in the thousands. Some high-dimensional problems can be solved efficiently to within ε, i.e., the cost increases polynomially in ε−1 and d. However, there are many multivariate problems for which even the minimal cost increases exponentially in d. This exponential dependence on d is called intractability or the curse of dimensionality . This is the first of a three-volume set comprising a comprehensive study of the tractability of multivariate problems. It is devoted to algorithms using linear information consisting of arbitrary linear functionals. The theory for multivariate problems is developed in various settings: worst case, average case, randomized and probabilistic. A problem is tractable if its minimal cost is not exponential in ε−1 and d. There are various notions of tractability, depending on how we measure the lack of exponential dependence. For example, a problem is polynomially tractable if its minimal cost is polynomial in ε−1 and d. The study of tractability was initiated about 15 years ago. This is the first research monograph on this subject. Many multivariate problems suffer from the curse of dimensionality when they are defined over classical (unweighted) spaces. But many practically important problems are solved today for huge d in a reasonable time. One of the most intriguing challenges of theory is to understand why this is possible. Multivariate problems may become tractable if they are defined over weighted spaces with properly decaying weights. In this case, all variables and groups of variables are moderated by weights. The main purpose of this book is to study weighted spaces and to obtain conditions on the weights that are necessary and sufficient to achieve various notions of tractability. The book is of interest for researchers working in computational mathematics, especially in approx

关键词： Curse of dimensionality tractability high-dimensional numerical problems worst case setting average case setting randomized algorithms weighted norms product weights finite-order weights

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Probabilistic Optimal Robust Performance Controller Design

引用

Journal of Beijing Institute of Technology 2004年第1期13卷 15-19页

作者：宋春雷谢玲 School of Information Science and Technology Beijing Institute of Technology Beijing100081 China

Polynomial-time randomized algorithms were constructed to approximately solve optimal robust performance controller design problems in probabilistic sense and the rigorous mathematical justification of the approach was given. The randomized algorithms here were based on a property from statistical learning theory known as (uniform) convergence of empirical means (UCEM). It is argued that in order to assess the performance of a controller as the plant varies over a pre-specified family, it is better to use the average performance of the controller as the objective function to be optimized, rather than its worst-case performance. The approach is illustrated to be efficient through an example.

关键词： randomized algorithms statistical learning theory uniform convergence of empirical means (UCEM) probabilistic optimal robust performance controller design

来源：评论

学校读者我要写书评

暂无评论

randomized protocols for duplicate elimination in peer-to-peer storage systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2007年第5期18卷 686-696页

作者： Ferreira, Ronaldo A. Ramanathan, Murali K. Grama, Ananth Jagannathan, Suresh Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Distributed peer-to-peer systems rely on voluntary participation of peers to effectively manage a storage pool. In such systems, data is generally replicated for performance and availability. If the storage associated with replication is not monitored and provisioned, the underlying benefits may not be realized. Resource constraints, performance scalability, and availability present diverse considerations. Availability and performance scalability, in terms of response time, are improved by aggressive replication, whereas resource constraints limit total storage in the network. Identification and elimination of redundant data pose fundamental problems for such systems. In this paper, we present a novel and efficient solution that addresses availability and scalability with respect to management of redundant data. Specifically, we address the problem of duplicate elimination in the context of systems connected over an unstructured peer-to-peer network in which there is no a priori binding between an object and its location. We propose two randomized protocols to solve this problem in a scalable and decentralized fashion that does not compromise the availability requirements of the application. Performance results using both large-scale simulations and a prototype built on PlanetLab demonstrate that our protocols provide high probabilistic guarantees while incurring minimal administrative overheads.

关键词： peer-to-peer unstructured networks duplicate elimination randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Guaranteed cost regulator design: A probabilistic solution and a randomized algorithm

引用

AUTOMATICA 2007年第2期43卷 317-324页

作者： Fujisaki, Yasumasa Oishi, Yasuaki Kobe Univ Dept Syst & Comp Engn Nada Ku Kobe Hyogo 6578501 Japan Univ Tokyo Dept Math Informat Bunkyo Ku Tokyo 1138656 Japan

This paper presents a gradient-based randomized algorithm to design a guaranteed cost regulator for a plant with general parametric uncertainties. The algorithm either provides with high confidence a probabilistic solution that satisfies the design specification with high probability for a randomly sampled uncertainty or claims that the feasible set of the design parameters is too small to contain a ball with a given radius. In both cases, the number of iterations executed in the algorithm is of polynomial order of the problem size and is independent of the dimension of the uncertainty. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： guaranteed cost regulator probabilistic approach randomized algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for a tensor-based generalization of the singular value decomposition

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2007年第2-3期420卷 553-571页

作者： Drineas, Petros Mahoney, Michael W. Yale Univ Dept Math New Haven CT 06520 USA Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

An algorithm is presented and analyzed that, when given as input a d-mode tensor A, computes an approximation (A) over tilde. The approximation (A) over tilde is computed by performing the following for each of the d modes: first, form (implicitly) a matrix by "unfolding" the tensor along that mode;then, choose columns from the matrices thus generated;and finally, project the tensor along that mode onto the span of those columns. An important issue affecting the quality of the approximation is the choice of the columns from the matrices formed by "unfolding" the tensor along each of its modes. In order to address this issue, two algorithms of independent interest are presented that, given an input matrix A and a target rank k, select columns that span a space close to the best rank k subspace of the matrix. For example, in one of the algorithms, a number c (that depends on k, an error parameter epsilon, and a failure probability delta) of columns are chosen in c independent random trials according to a nonuniform probability distribution depending on the Euclidean lengths of the columns. When this algorithm for choosing columns is used in the tensor approximation, then under appropriate assumptions bounds of the form parallel to A-A parallel to(F) <= (d)Sigma(i=1) parallel to A([i])-(A([i]))k(i) parallel to(F) +d epsilon parallel to(F)+parallel to A parallel to(F) are obtained, where A([i]) is the matrix formed by "unfolding" the tensor along the ith mode and where (A([i]))k(i) is the best rank k(i) approximation to the matrix A([i]). Each parallel to A([i]) - (A([i]))k(i) parallel to(F) term is a measure of the extent to which the matrix A([i]) is not well-approximated by a rank-k(i) matrix, and the epsilon parallel to A parallel to(F) term is a measure of the loss in approximation quality due to the choice of columns (rather than, e.g., the top k(i) singular vectors along each mode). Bounds of a similar form are obtained with the other column selection algorithm.

关键词： tensor decomposition CUR decomposition randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved lower bounds on the randomized complexity of graph properties

引用

RANDOM STRUCTURES & algorithms 2007年第3期30卷 427-440页

作者： Chakrabarti, Amit Khot, Subhash Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

We prove a lower bound of Omega(n(4/3) log(1/3) n) on the randomized decision tree complexity of any nontrivial monotone n-vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size it. This improves the previous best bound of Omega(n(4/3)) due to Hajnal (Combinatorica 11 (1991) 131-143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest. (c) 2007 Wiley Periodicals, Inc.

关键词： decision trees graph properties complexity randomized algorithms graph packing probabilistic method

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Asynchronous randomized Consensus 07

Tight Bounds for Asynchronous Randomized Consensus

引用

39th Annual ACM Symposium on Theory of Computing

作者： Attiya, Hagit Censor, Keren Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781595936318

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all *** work proves that the total step complexity of randomized consensus is Θ(n2) in an asynchronous shared memory systemusing multi-writer multi-reader registers. The bound is achieved by improving both the lower and the upper bounds for this *** addition to improving upon the best previously known result bya factor of log2 n, the lower bound features agreatly streamlined proof. Both goals are achieved through restricting attention to a set of layered executions andusing an isoperimetric inequality for analyzing their *** matching algorithm decreases the expected total step complexity by a log n factor, by leveraging themulti-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithmas a stochastic process and applying Kolmogorov's inequality.

关键词： lower bound shared-memory distributed computing randomized algorithms isoperimetric inequality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：