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

作者： Liu, Yao Texas A&M University

学位级别：硕士

This thesis studies the problem of content distribution in wireless peer-to-peer networks with selfish nodes. In this problem a group of wireless nodes need to exchange a set of files over a lossless broadcast channel. Each node aims to maximize its own download rate and minimize its upload rate. We propose a distributed protocol that provides incentives for selfish nodes to participate in the content exchange. Our protocol does not require any exchange of money and reputation and hence can be easily implemented without additional infrastructure. Then, we will analyze the performance of our protocol by focusing on the import-ant case in which the system contains two files that need to be distributed. We derive a closed-form expression of Nash Equilibrium and characterize the corresponding system performance in discrete time. Furthermore, we propose a distributed mechanism where the strategy of each node is only based on the observed history of the system and not on the private information of other nodes. We also study the performance characteristics of the systems that employ network coding to facilitate data exchange. We show that, due to the free rider problem network coding does not necessary improve the performance of the system and, in some cases, may lead to worse system performance. We propose a novel approach to this problem based on random coding. The performance of the network coding algorithms is validated by performing extensive simulation study.

关键词： Peer-to-Peer Wireless Game Theory Network Coding randomized algorithm Thesis

来源：评论

学校读者我要写书评

暂无评论

Fast Matrix Rank algorithms and Applications

引用

JOURNAL OF THE ACM 2013年第5期60卷 31-31页

作者： Cheung, Ho Yee Kwok, Tsz Chiu Lau, Lap Chi Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

We consider the problem of computing the rank of an m x n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in (O) over tilde(vertical bar A vertical bar + r(omega)) field operations, where vertical bar A vertical bar denotes the number of nonzero entries in A and omega < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with deterministic running time O(mnr(omega-2)). Our algorithm is faster when r < max{m, n}, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in (O) over tilde (mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in exact linear algebra, combinatorial optimization and dynamic data structure.

关键词： algorithms Theory Combinatorial optimization exact linear algebra matrix rank randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient symmetry-based screening strategy to speed up randomized circle-detection

引用

PATTERN RECOGNITION LETTERS 2012年第16期33卷 2071-2076页

作者： Huang, Yong-Huai Chung, Kuo-Liang Yang, Wei-Ning Chiu, Shih-Hsuan Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei 10672 Taiwan Jinwen Univ Sci & Technol Inst Comp & Commun Engn New Taipei City 23154 Taiwan Jinwen Univ Sci & Technol Dept Elect Engn New Taipei City 23154 Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 10672 Taiwan Natl Taiwan Univ Sci & Technol Dept Mat Sci & Engn Taipei 10672 Taiwan

randomized approaches for circle detections are often used for the advantages of less computational time and memory requirements. However, randomized approaches involve examining a large number of candidate circles and may not be suitable for real-time applications. In this paper, a screening strategy based on the symmetric property of the circle is adopted to select the promising candidates for further investigation, resulting in substantial reduction in the computational time while maintaining the accuracy. Empirical results show that, under the same accuracy level, the proposed symmetry-based method achieves the improvement ratios of 40%-90% on the execution-time when compared to four state-of-the-art randomized methods. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Circle detection Computation-saving Hough transform randomized algorithm Screening strategy

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for the joining protocol in dynamic distributed networks

引用

THEORETICAL COMPUTER SCIENCE 2008年第3期406卷 248-262页

作者： Cooper, Colin Klasing, Ralf Radzik, Tomasz Univ Bordeaux 1 CNRS LaBRI F-33405 Talence France Kings Coll London Dept Comp Sci London WC2R 2LS England

We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. One model we consider is a network constructed in this fashion, in which vertices join but never leave. If t is the size of the network, then the diameter of the network is O(log t) for all t, with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t(1/2+delta). With high probability the network reconnects itself by replacing lost edges using tokens from the token pool. (c) 2008 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Dynamic network joining protocol Random graph process Overlay network Random walks Peer to peer networks Self repairing networks

来源：评论

学校读者我要写书评

暂无评论

Information-Based Complexity of Integration in the randomized and Quantum Computation Model

Information-Based Complexity of Integration in the Randomize...

引用

7th International Conference on MEMS, NANO and Smart Systems (ICMENS 2011)

作者： Gao Wenhua Duan Liqin Zhou Wei Ye Peixin Beijing Normal Univ Zhuhai Sch Appl Math Zhuhai 519087 Peoples R China Hangzhou Dianzi Univ Inst Math Hangzhou 310018 Peoples R China Nankai Univ Sch Math & LPMC Tianjin 300071 Peoples R China

ISBN: (纸本)9783037853122

In this paper, we investigate the integration of the Holder-Nikolskii classes MHpr in the randomized and quantum computation model. We develop randomized and quantum algorithms for integration of functions from this class and analyze their convergence rates. Comparing our result with the convergence rates in the deterministic setting, we see that quantum computing can reach an exponential speedup over deterministic classical computation and a quadratic speedup over randomized classical computation..

关键词： randomized algorithm Quantum algorithm Holder-Nikolskii class Convergence rate

来源：评论

学校读者我要写书评

暂无评论

Fast Approximation of Matrix Coherence and Statistical Leverage

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2012年 13卷 3475-3506页

作者： Drineas, Petros Magdon-Ismail, Malik Mahoney, Michael W. Woodruff, David P. Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA Stanford Univ Dept Math Stanford CA 94305 USA IBM Almaden Res Ctr San Jose CA 95120 USA

The statistical leverage scores of a matrix A are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nystrom-based low-rank matrix approximation as well as in large-scale statistical data analysis applications more generally;moreover, they are of interest since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n x d matrix A, with n >> d, and that returns as output relative-error approximations to a l l n of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of n and d) in O(nd log n) time, as opposed to the O (n d 2) time required by the naive algorithm that involves computing an orthogonal basis for the range of A. Our analysis may be viewed in terms of computing a relative-error approximation to an under constrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with n approximate to d, and the extension to streaming environments.

关键词： matrix coherence statistical leverage randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

On derandomization and average-case complexity of monotone functions

引用

THEORETICAL COMPUTER SCIENCE 2012年 434卷 35-44页

作者： Karakostas, George Kinne, Jeff van Melkebeek, Dieter Indiana State Univ Terre Haute IN 47809 USA McMaster Univ Hamilton ON L8S 4L8 Canada Univ Wisconsin Madison WI 53706 USA

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions - that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Derandomization Monotone circuits Monotone functions randomized algorithm Pseudorandom generators Average-case complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient Decentralized algorithms for the Distributed Trigger Counting Problem

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期51卷 447-473页

作者： Chakaravarthy, Venkatesan T. Choudhury, Anamitra R. Garg, Vijay K. Sabharwal, Yogish IBM Res India New Delhi India Univ Texas Austin Austin TX 78712 USA

Consider a distributed system with n processors, in which each processor receives some triggers from an external source. The distributed trigger counting (DTC) problem is to raise an alert and report to a user when the number of triggers received by the system reaches w, where w is a user-specified input. The problem has applications in monitoring, global snapshots, synchronizers and other distributed settings. In this paper, we first present a randomized and decentralized algorithm for the DTC problem with message complexity O(nlognlogw);furthermore, with high probability, no processor receives more than O(lognlogw) messages. Building on the ideas of this algorithm, we develop an improved algorithm having message complexity O(nlogw);furthermore, with high probability, no processor receives more than O(log w) messages. However, neither of the two algorithms provide any bound on the messages sent per processors. These algorithm assume complete connectivity between the processors. Next, we present a third algorithm having message complexity O(nlognlogw), wherein no processor exchanges more than O(lognlogw) messages with high probability;however, there is a negligible failure probability in raising the alert on receiving w triggers. This algorithm only requires that a constant degree tree be embeddable in the underlying communication graph.

关键词： Distributed trigger counting randomized algorithm Message complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient Information Exchange in Single-Hop Multi-Channel Radio Networks

Efficient Information Exchange in Single-Hop Multi-Channel R...

引用

7th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Shi, Weijie Hua, Qiang-Sheng Yu, Dongxiao Wang, Yuexuan Lau, Francis C. M. Tsinghua Univ Inst Interdisciplinary Informat Sci Inst Theoret Comp Sci Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

ISBN: (纸本)9783642318696

This paper studies the information exchange problem in single-hop multi-channel radio networks, which is to disseminate k messages stored in k arbitrary nodes to the entire network (with n nodes) with the fewest timeslots. By using Theta(root n) channels, the previous best result [9] showed that this problem can be solved in Theta(k) time slots with high probability even if k is unknown and no bounds on k are given. Under the same assumptions but by using Theta(n) channels, this paper presents a novel randomized distributed algorithm called Detect-and-Drop that can solve the information exchange problem in O(log k log log k) time slots with high probability. Thus by allowing using more channels, our proposed algorithm contributes an exponential improvement in running time compared to that in [9]. The simulation results corroborate the analysis result.

关键词： information exchange single hop multiple channels randomized algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

ONLINE SET PACKING

引用

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 728-746页

作者： Emek, Yuval Halldorsson, Magnus M. Mansour, Yishay Patt-Shamir, Boaz Radhakrishnan, Jaikumar Rawitz, Dror ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland Reykjavik Univ Sch Comp Sci IS-103 Reykjavik Iceland Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

关键词： online set packing competitive analysis randomized algorithm packet fragmentation multipacket frames

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：