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

21st Annual Symposium on Computational Geometry

作者： Frahling, Gereon Indyk, Piotr Sohler, Christian Google Res New York NY 10011 USA MIT Lab Comp Sci & Artificial Intelligence Cambridge MA 02139 USA Univ Gesamthsch Paderborn Heinz Nixdorf Inst D-4790 Paderborn Germany Univ Gesamthsch Paderborn Dept Comp Sci D-4790 Paderborn Germany

A dynamic geometric data stream is a sequence of m ADD/REMOVE operations of points from a discrete geometric space {1, ... , Delta}(d) ?. ADD ( p) inserts a point p from {1, ..., Delta}(d) into the current point set P, REMOVE(p) deletes p from P. We develop low-storage data structures to ( i) maintain e- nets and e- approximations of range spaces of P with small VC-dimension and (ii) maintain a ( 1 + e)- approximation of the weight of the Euclidean minimum spanning tree of P. Our data structure for epsilon-nets uses O((log(1/delta)/epsilon + D/epsilon log D/epsilon) center dot d(2) center dot log (2)(Delta/delta)) bits of memory and returns with probability 1 - delta a set of (O) over tilde D+log(1/delta)/epsilon) points that is an epsilon-net for an arbitrary fixed finite range space with VC-dimension D-a. Our data structure for epsilon-approximations uses (O) over tilde D+log(1/delta)/epsilon(2)) center dot d(2) center dot log (2)(Delta/delta) + log(2) (1/delta)) bits of memory and returns with probability 1- delta a set of (O) over tilde D+log(1/delta)/epsilon(2)) points that is an epsilon-approximation for an arbitrary fixed finite range space with VC-dimension D. The data structure for the approximation of the weight of a Euclidean minimum spanning tree uses O(log (1/delta)(log Delta/epsilon)(O[d])) space and is correct with probability at least 1 - delta. Our results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.

关键词： Data streaming Minimum spanning trees Random sampling randomized algorithms ε-approximations ε-nets

来源：评论

学校读者我要写书评

暂无评论

On Spreading Recommendations via Social Gossip 08

On Spreading Recommendations via Social Gossip

引用

20th ACM Symposium on Parallelism in algorithms and Architectures

作者： Fernandess, Yaacov Man, Dahlia Hebrew Univ Jerusalem Sch Engn & Comp Sci IL-91905 Jerusalem Israel

ISBN: (纸本)9781595939739

This paper introduces and analyzes a variant of distributed gossip which is motivated by the sharing of recommendations in a social network. The social settings bear two implications oil gossip. First, rumors fade after a few hops, and so does our gossip mechanism. Second, users require a rumor to be substantiated by multiple, independent sources in order to adopt it. Consequently, in our social gossip a message is adopted only when it is received over a threshold of independent paths. Social gossip is a new, highly relevant and practically motivated variant of distributed gossip, whose analysis contributes to the fundamental theory of distributed algorithms.

关键词： randomized algorithms message dissemination gossip algorithms epidemic algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of linear programming decoding 18

Probabilistic analysis of linear programming decoding

引用

18th ACM-SIAM Symposium on Discrete algorithms

作者： Daskalakis, Constantinos Dimakis, Alexandros G. Karp, Richard M. Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94704 USA

ISBN: (纸本)9780898716245

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous nonasymptotic results for LDPC codes, and in particular, exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on the Tanner graph of the code. An interesting by-product of our analysis is to establish the existence of "probabilistic expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst case setting.

关键词： binary-symmetric channel (BSC) channel coding error-control coding expanders factor graphs linear programming decoding low-density parity-check (LDPC) codes randomized algorithms sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Scalable Approximate Query Processing with the DBO Engine

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2008年第4期33卷 23:1-23:54页

作者： Jermaine, Chris Arumugam, Subramanian Pol, Abhijit Dobra, Alin Univ Florida Gainesville FL 32611 USA

This article describes query processing in the DBO database system. Like other database systems designed for ad hoc analytic processing, DBO is able to compute the exact answers to queries over a large relational database in a scalable fashion. Unlike any other system designed for analytic processing, DBO can constantly maintain a guess as to the final answer to an aggregate query throughout execution, along with statistically meaningful bounds for the guess's accuracy. As DBO gathers more and more information, the guess gets more and more accurate, until it is 100% accurate as the query is completed. This allows users to stop the execution as soon as they are happy with the query accuracy, and thus encourages exploratory data analysis.

关键词： algorithms Performance Online aggregation sampling randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Dense Subgraph Problems with Output-Density Conditions

引用

ACM TRANSACTIONS ON algorithms 2008年第4期4卷 1–18页

作者： Suzuki, Akiko Tokuyama, Takeshi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized PTAS, even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o(n) vertices.

关键词： Combinatorial optimization dense subgraph approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Archipelago: Trading address space for reliability and security

引用

ACM SIGPLAN NOTICES 2008年第3期43卷 115-124页

作者： Lvin, Vitaliy B. Novark, Gene Berger, Emery D. Zorn, Benjamin G. Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Microsoft Res Redmond WA 98052 USA

Memory errors are a notorious source of security vulnerabilities that can lead to service interruptions, information leakage and unauthorized access. Because such errors are also difficult to debug, the absence of timely patches can leave users vulnerable to attack for long periods of time. A variety of approaches have been introduced to combat these errors, but these often incur large runtime overheads and generally abort on errors, threatening availability. This paper presents Archipelago, a runtime system that takes advantage of available address space to substantially reduce the likelihood that a memory error will affect program execution. Archipelago randomly allocates heap objects far apart in virtual address space, effectively isolating each object from buffer overflows. Archipelago also protects against dangling pointer errors by preserving the contents of freed objects after they are freed. Archipelago thus trades virtual address space-a plentiful resource on 64-bit systems-for significantly improved program reliability and security, while limiting physical memory consumption by tracking the working set of an application and compacting cold objects. We show that Archipelago allows applications to continue to run correctly in the face of thousands of memory errors. Across a suite of server applications, Archipelago's performance overhead is 6% on average (between -7% and 22%), making it especially suitable to protect servers that have known security vulnerabilities due to heap memory errors.

关键词： algorithms languages reliability security Archipelago buffer overflow dynamic memory allocation memory errors probabilistic memory safety randomized algorithms virtual memory

来源：评论

学校读者我要写书评

暂无评论

The Scenario Approach for Systems and Control Design

引用

IFAC Proceedings Volumes 2008年第2期41卷 381-389页

作者： Marco C. Campi Simone Garatti Maria Prandini Dipartimento di Elettronica per l'Automazione Università degli Studi di Brescia Italy Dipartimento di Elettronica e Informazione Politecnico di Milano Italy

The ‘scenario approach’ is an innovative technology that has been introduced to solve convex optimization problems with an infinite number of constraints, a class of problems which often occurs when dealing with uncertainty. This technology relies on random sampling of constraints, and provides a powerful means for solving a variety of design problems in systems and control. The objective of this paper is to illustrate the scenario approach at a tutorial level, focusing mainly on algorithmic aspects. Specifically, its versatility and virtues will be pointed out through a number of examples in model reduction, robust and optimal control.

关键词： Systems and control design Robust convex optimization Probabilistic methods randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic sorting and stabilization of switched systems

引用

IFAC Proceedings Volumes 2008年第2期41卷 402-407页

作者： Hideaki Ishii Roberto Tempo Department of Computational Intelligence and Systems Science Tokyo Institute of Technology Yokohama 226-8502 Japan IEIIT-CNR Politecnico di Torino 10129 Torino Italy

We consider Lyapunov stability of switched linear systems whose switching signal is constrained to a subset of indices. We propose a switching rule that chooses the most stable subsystem among those belonging to the subset. This rule is based on an ordering of the subsystems using a common Lyapunov function. We develop randomized algorithms for finding the ordering as well as for finding a subset of systems for which a common Lyapunov function exists. We show that the class of Las Vegas randomized algorithms is useful in the design.

关键词： Switched systems Lyapunov function randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for quadratic stability of quantized sampled-data systems

引用

AUTOMATICA 2004年第5期40卷 839-846页

作者： Ishii, H Basar, TB Tempo, R Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Politecn Torino CNR IEIIT I-10129 Turin Italy

In this paper, we present a novel development of randomized algorithms for quadratic stability analysis of sampled-data systems with memoryless quantizers. The specific randomized algorithm employed generates a quadratic Lyapunov function and leads to realistic bounds on the performance of such systems. A key feature of this method is that the characteristics of quantizers are exploited to make the algorithm computationally efficient. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： quadratic stability quantizers randomized algorithms sampled-data systems

来源：评论

学校读者我要写书评

暂无评论

Approximating power indices 08

Approximating power indices

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：