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

QUANTUM INFORMATION PROCESSING 2015年第6期14卷 1777-1785页

作者： Bera, Debajyoti Indraprastha Inst Informat Technol IIIT D New Delhi 110020 India

One of the early achievements of quantum computing was demonstrated by Deutsch and Jozsa (Proc R Soc Lond A Math Phys Sci 439(1907):553, 1992) regarding classification of a particular type of Boolean functions. Their solution demonstrated an exponential speedup compared to classical approaches to the same problem;however, their solution was the only known quantum algorithm for that specific problem so far. This paper demonstrates another quantum algorithm for the same problem, with the same exponential advantage compared to classical algorithms. The novelty of this algorithm is the use of quantum amplitude amplification, a technique that is the key component of another celebrated quantum algorithm developed by Grover (Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM Press, New York, 1996). A lower bound for randomized (classical) algorithms is also presented which establishes a sound gap between the effectiveness of our quantum algorithm and that of any randomized algorithm with similar efficiency.

关键词： Quantum algorithm Deutsch-Jozsa Amplitude amplification Lower bound randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The probabilistic approach to limited packings in graphs

引用

DISCRETE APPLIED MATHEMATICS 2015年 184卷 146-153页

作者： Gagarin, Andrei Zverovich, Vadim Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ W England Bristol BS16 1QY Avon England

We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k-limited packing if for every vertex v is an element of V (G), vertical bar N[v] boolean AND X vertical bar <= k, where N[v] is the closed neighbourhood of v. The k-limited packing number L-k(G) of a graph G is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new application of the probabilistic method to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree Delta. L-k(G) >= kn/(k+1) (k)root((Delta)(k)) (Delta+1) Also, some other upper and lower bounds for L-k (G) are given. (C) 2014 Elsevier B.V. All rights reserved.

关键词： k-limited packings The probabilistic method Lower and upper bounds randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The Staircase Mechanism in Differential Privacy

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2015年第7期9卷 1176-1184页

作者： Geng, Quan Kairouz, Peter Oh, Sewoong Viswanath, Pramod Tower Res Capital LLC New York NY 10081 USA Univ Illinois Coordinated Sci Lab Urbana IL 61820 USA Univ Illinois Ind & Enterprise Syst Engn Dept Urbana IL 61820 USA

Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves;the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).

关键词： Data privacy randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

BUTTERFLY FACTORIZATION

引用

MULTISCALE MODELING & SIMULATION 2015年第2期13卷 714-732页

作者： Li, Yingzhou Yang, Haizhao Martin, Eileen R. Ho, Kenneth L. Ying, Lexing Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA

The paper introduces the butterfly factorization as a data-sparse approximation for the matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorithms for applying the matrix and its adjoint are available or the entries of the matrix can be sampled individually. For an N x N matrix, the resulting factorization is a product of O(log N) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.

关键词： data-sparse matrix butterfly algorithm randomized algorithm matrix factorization operator compression Fourier integral operators special functions

来源：评论

学校读者我要写书评

暂无评论

Content Placement and Service Scheduling in Femtocell Caching Networks

Content Placement and Service Scheduling in Femtocell Cachin...

引用

IEEE Global Communications Conference

作者： Teng Liu Alhussein A. Abouzeid Department of Electrical Computer and Systems Engineering Rensselaer Polytechnic Institute

ISBN: (纸本)9781509013296

This work considers the joint problem of content placement and service scheduling in femtocell caching networks, to maximize the traffic volume served from the cache. The problem is modeled as a Markov decision process. We combine the Edmonds-Karp algorithm and the marginal allocation algorithm to develop an efficient centralized policy called Infinite CAche-filling (ICA), which can get arbitrarily close to optimal asymptotically as the estimation time window increases. We also design a randomized algorithm called Infinite CAche-filling with Probabilistic scheduling (ICAP) that takes into consideration the femtocells service capability due to interference or multiplexing techniques. We derive a lower bound on the expected discounted hit count of ICAP. We also derive an upper bound on the probability that the performance of ICAP degrades from this expected value. Numerical results show that ICAP scales well and converges relatively fast in response to request pattern changes.

关键词： Content-centric networking Femtocell network Markov decision process randomized algorithm randomized algorithms Markov chain Femtocell networks Femtocells Allocation algorithm Cache memory Traffic volume Content distribution

来源：评论

学校读者我要写书评

暂无评论

randomized Pattern Formation algorithm for Asynchronous Oblivious Mobile Robots 28

Randomized Pattern Formation Algorithm for Asynchronous Obli...

引用

28th International Symposium on Distributed Computing

作者： Yamauchi, Yukiko Yamashita, Masafumi Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka 812 Japan

ISBN: (纸本)9783662451748

We present a randomized pattern formation algorithm for asynchronous oblivious (i.e., memory-less) mobile robots that enables formation of any target pattern. As for deterministic pattern formation algorithms, the class of patterns formable from an initial configuration I is characterized by the symmetricity (i.e., the order of rotational symmetry) of I, and in particular, every pattern is formable from I if its symmetricity is 1. The randomized pattern formation algorithm psi(PF) we present in this paper consists of two phases: The first phase transforms a given initial configuration I into a configuration I' such that its symmetricity is 1, and the second phase invokes a deterministic pattern formation algorithm psi(CWM) by Fujinaga et al. (DISC 2012) for asynchronous oblivious mobile robots to finally form the target pattern. There are two hurdles to overcome to realize psi(PF). First, all robots must simultaneously stop and agree on the end of the first phase, to safely start the second phase, since the correctness of psi(CWM) is guaranteed only for an initial configuration in which all robots are stationary. Second, the sets of configurations in the two phases must be disjoint, so that even oblivious robots can recognize which phase they are working on. We provide a set of tricks to overcome these hurdles.

关键词： Mobile robot pattern formation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Statistical Perspective on algorithmic Leveraging

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2015年第1期16卷 861-911页

作者： Ma, Ping Mahoney, Michael W. Yu, Bin Univ Georgia Dept Stat Athens GA 30602 USA Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method. In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance, both conditional and unconditional on the observed data. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling. Based on these theoretical results, we propose and analyze two new leveraging algorithms: one constructs a smaller least-squares problem with "shrinkage" leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical result

关键词： randomized algorithm leverage scores subsampling least squares linear regression

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for the efficient synthesis of heat exchanger networks

引用

COMPUTERS & CHEMICAL ENGINEERING 2010年第10期34卷 1632-1639页

作者： Gupta, Abhigyan Ghosh, Pallab Indian Inst Technol Guwahati Dept Chem Engn Gauhati 781039 Assam India

This article presents an algorithm for the synthesis of heat exchanger networks (HENs) using randomization as an effective tool. It optimizes the total cost of the network. The method proposed here is suitable for finding the optimal solution with stream-splitting and merging. The present approach provides significant advantage of randomization over other existing optimization techniques for obtaining the optimal solution. We have studied three benchmark problems already published in the literature to demonstrate how better solutions were undetected by the earlier approaches. The salient feature of the proposed algorithm is that it provides a variety of possible networks which are close to the optimal network. Another important aspect is that the algorithm is quite fast. For small-and medium-size problems, the technique proposed in this article will prove to be very effective for the design of heat exchanger networks. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Cost optimization CPU time Heat exchanger network synthesis Optimum network randomized algorithm Stream-splitting

来源：评论

学校读者我要写书评

暂无评论

algorithms and Stability Analysis for Content Distribution over Multiple Multicast Trees

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2015年第5期26卷 1217-1227页

作者： Zheng, Xiaoying Cho, Chunglae Xia, Ye Chinese Acad Sci Shanghai Adv Res Inst Beijing 100864 Peoples R China Shanghai Res Ctr Wireless Commun Shanghai Peoples R China Elect & Telecommun Res Inst Beijing Peoples R China Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

The paper investigates theoretical issues in applying the universal swarming technique to efficient content distribution. In a swarming session, a file is distributed to all the receivers by having all the nodes in the session exchange file chunks. By universal swarming, not only all the nodes in the session, but also some nodes outside the session may participate in the chunk exchange to improve the distribution performance. We present a universal swarming model where the chunks are distributed along different Steiner trees rooted at the source and covering all the receivers. We assume chunks arrive dynamically at the sources and focus on finding stable universal swarming algorithms. To achieve the throughput region, universal swarming usually involves a tree-selection subproblem of finding a min-cost Steiner tree, which is NP-hard. We propose a universal swarming scheme that employs an approximate tree-selection algorithm. We show that it achieves network stability for a reduced throughput region, where the reduction ratio is no more than the approximation ratio of the tree-selection algorithm. We propose a second universal swarming scheme that employs a randomized tree-selection algorithm. It achieves the throughput region, but with a weaker stability result. Comprehensive simulation results support the stability analysis of the algorithms. The proposed schemes and their variants are expected to be useful for infrastructure-based content distribution networks with massive content and relatively stable network environment.

关键词： Communication networks multicast stability queueing randomized algorithm content distribution

来源：评论

学校读者我要写书评

暂无评论

Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme

引用

控制理论与技术（英文版） 2015年第4期13卷 333-347页

作者： Peng YI Yiguang HONG Key Lab of Systems and Control Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China

In this paper, we consider a distributed convex optimization problem of a multi-agent system with the global objective function as the sum of agents’ individual objective functions. To solve such an optimization problem, we propose a distributed stochastic sub-gradient algorithm with random sleep scheme. In the random sleep scheme, each agent independently and randomly decides whether to inquire the sub-gradient information of its local objective function at each iteration. The algorithm not only generalizes distributed algorithms with variable working nodes and multi-step consensus-based algorithms, but also extends some existing randomized convex set intersection results. We investigate the algorithm convergence properties under two types of stepsizes: the randomized diminishing stepsize that is heterogeneous and calculated by individual agent, and the fixed stepsize that is homogeneous. Then we prove that the estimates of the agents reach consensus almost surely and in mean, and the consensus point is the optimal solution with probability 1, both under randomized stepsize. Moreover, we analyze the algorithm error bound under fixed homogeneous stepsize, and also show how the errors depend on the fixed stepsize and update rates.

关键词： Distributed optimization sub-gradient algorithm random sleep multi-agent systems randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：