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

randomized on-line and semi-on-line scheduling on identical machines

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2003年第1期20卷 31-40页

作者： He, Y Tan, ZY Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

This paper considers on-line and semi-on-line scheduling problems on m parallel machines with objective to maximize the minimum load. For on-line version, we prove that algorithm Random is an optimal randomized algorithm on two machines, and derive a new randomized upper bound for general m machines which significantly improves the known upper bound. For semi-on-line version with non-increasing job processing times, we show that LS algorithm is an optimal deterministic algorithm for two and three machine cases. We further present an optimal randomized algorithm RLS for two machine case.

关键词： on-line scheduling analysis of algorithm competitive ratio randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient randomized Switching for Maximizing Lifetime in Tree-Based Wireless Sensor Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2015年第5期23卷 1401-1415页

作者： Imon, Sk Kajal Arefin Khan, Adnan Di Francesco, Mario Das, Sajal K. Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA Aalto Univ Dept Comp Sci & Engn Aalto 00076 Finland Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA

In most wireless sensor network (WSN) applications, data are typically gathered by sensor nodes and reported to a data collection point called sink. To support such a data collection pattern, a tree structure rooted at the sink is defined. Depending on various factors, including the WSN topology and the availability of resources, the energy consumption of nodes in different paths of the data collection tree may vary largely, thus affecting the overall network lifetime. This paper addresses the problem of lifetime maximization of WSNs based on data collection trees. Specifically, we propose a novel and efficient algorithm, called randomized Switching for Maximizing Lifetime (RaSMaLai), that aims at extending the lifetime of WSNs through load balancing. Given an initial data collection tree, RaSMaLai randomly switches some sensor nodes from their original paths to other paths with lower load. We prove that, under appropriate settings of the operating parameters, RaSMaLai converges with a low time complexity. We further design a distributed version of our algorithm. Through an extensive performance evaluation study that includes simulation of large-scale scenarios and real experiments on a WSN testbed, we show that the proposed RaSMaLai algorithm and its distributed version achieve a longer network lifetime than the state-of-the-art solutions.

关键词： Data collection tree load balancing network lifetime randomized algorithm wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

On the mean square error of randomized averaging algorithms

引用

AUTOMATICA 2013年第8期49卷 2496-2501页

作者： Frasca, Paolo Hendrickx, Julien M. Politecn Torino Dept Math Sci I-10129 Turin Italy Catholic Univ Louvain ICTEAM Inst B-1348 Louvain Belgium

This paper considers randomized discrete-time consensus systems that preserve the average "on average". As a main result, we provide an upper bound on the mean square deviation of the consensus value from the initial average. Then, we apply our result to systems in which few or weakly correlated interactions take place: these assumptions cover several algorithms proposed in the literature. For such systems we show that, when the network size grows, the deviation tends to zero, and that the speed of this decay is not slower than the inverse of the size. Our results are based on a new approach, which is unrelated to the convergence properties of the system. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Consensus algorithm randomized algorithm Networked estimation

来源：评论

学校读者我要写书评

暂无评论

Fast randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra

引用

SIAM REVIEW 2017年第3期59卷 547-587页

作者： Lim, Lek-Heng Weare, Jonathan Univ Chicago Dept Stat Chicago IL 60637 USA Univ Chicago James Franck Inst Dept Stat 5640 S Ellis Ave Chicago IL 60637 USA

We review the basic outline of the highly successful diffusion Monte Carlo technique commonly used in contexts ranging from electronic structure calculations to rare event simulation and data assimilation, and propose a new class of randomized iterative algorithms based on similar principles to address a variety of common tasks in numerical linear algebra. From the point of view of numerical linear algebra, the main novelty of the fast randomized iteration schemes described in this article is that they have dramatically reduced operations and storage cost per iteration (as low as constant under appropriate conditions) and are rather versatile: we will show how they apply to the solution of linear systems, eigenvalue problems, and matrix exponentiation, in dimensions far beyond the present limits of numerical linear algebra. While traditional iterative methods in numerical linear algebra were created in part to deal with instances where a matrix (of size O(n(2))) is too big to store, the algorithms that we propose are effective even in instances where the solution vector itself (of size O(n)) may be too big to store or manipulate. In fact, our work is motivated by recent diffusion Monte Carlo based quantum Monte Carlo schemes that have been applied to matrices as large as 10(108) x 10(108). We provide basic convergence results, discuss the dependence of these results on the dimension of the system, and demonstrate dramatic cost savings on a range of test problems.

关键词： dimension reduction randomized algorithm eigenvalue problem matrix exponentiation diffusion Monte Carlo quantum Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

Efficient randomized web-cache replacement schemes using samples from past eviction times

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2002年第4期10卷 441-454页

作者： Psounis, K Prabhakar, B Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

The problem of document replacement in web caches has received much attention in recent research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for, approximating any existing web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M < N least useful documents are retained for the succeeding iteration. When the next replacement is to be performed, the algorithm obtains N - M new samples from the cache and replaces the least useful document from the N - M new samples and the M previously retained. Using theory and simulations, we analyze the algorithm and find that it matches the performance of existing document replacement schemes for values of N and M as low as 8 and 2 respectively. Interestingly, we find. that retaining. a small number of samples from one iteration to the next leads to an exponential improvement in performance as compared to retaining no samples at all.

关键词： Cache replacement scheme past samples randomized algorithm Web caching

来源：评论

学校读者我要写书评

暂无评论

randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time

引用

MATHEMATICS OF OPERATIONS RESEARCH 2020年第2期45卷 517-546页

作者： Wang, Mengdi Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08540 USA

We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted-reward and average-reward Markov decision problems. By leveraging the value-policy duality, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an f-optimal policy using nearly linear runtime in the worst case for a fixed value of the discount factor. When the Markov decision process is ergodic and specified in some special data formats, for fixed values of certain ergodicity parameters, the algorithm finds an c-optimal policy using sample size and time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.

关键词： Markov decision process randomized algorithm linear programming duality primal-dual method runtime complexity stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

randomized Gathering of Mobile Agents in Anonymous Unidirectional Ring Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第5期25卷 1289-1296页

作者： Ooshita, Fukuhito Kawai, Shinji Kakugawa, Hirotsugu Masuzawa, Toshimitsu Osaka Univ Sch Informat Sci & Technol Suita Osaka 5650871 Japan

We consider the gathering problem of multiple (mobile) agents in anonymous unidirectional ring networks under the constraint that each agent knows neither the number of nodes nor the number of agents. For this problem, we fully characterize the relation between probabilistic solvability and termination detection. First, we prove for any (small) constant p (0 < p <= 1) that no randomized algorithm exists that solves, with probability p, the gathering problem with (termination) detection. For this reason, we consider the relaxed gathering problem, called the gathering problem without detection, which does not require termination detection. We propose a randomized algorithm that solves, with any given constant probability p (0 < p < 1), the gathering problem without detection. Finally, we prove that no randomized algorithm exists that solves, with probability 1, the gathering problem without detection.

关键词： Mobile agents gathering problem randomized algorithm ring networks

来源：评论

学校读者我要写书评

暂无评论

Hypergraph k-cut in randomized polynomial time

引用

MATHEMATICAL PROGRAMMING 2021年第1-2期186卷 85-113页

作者： Chandrasekaran, Karthekeyan Xu, Chao Yu, Xilin Univ Illinois Champaign IL 61820 USA Yahoo Res New York NY USA

For a fixed integer the hypergraph k-cut problem asks for a smallest subset of hyperedges whose removal leads to at least k connected components in the remaining hypergraph. While graph k-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24-37, 1994), the complexity of hypergraph k-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraph k-cut problem. Our algorithmic technique extends to solve the more general hedge k-cut problem when the subgraph induced by every hedge has a constant number of connected components. Our algorithm is based on random contractions akin to Karger's min cut algorithm. Our main technical contribution is a non-uniform distribution over the hedges (hyperedges) so that random contraction of hedges (hyperedges) chosen from the distribution succeeds in returning an optimum solution with large probability. In addition, we present an alternative contraction based randomized polynomial time approximation scheme for hedge k-cut in arbitrary hedgegraphs (i.e., hedgegraphs whose hedges could have a large number of connected components). Our algorithm and analysis also lead to bounds on the number of optimal solutions to the respective problems.

关键词： Hypergraph-k-cut Hedgegraph-k-cut randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-rank approximation of large-scale matrices via randomized methods

引用

JOURNAL OF SUPERCOMPUTING 2018年第2期74卷 830-844页

作者： Hatamirad, Sarvenaz Pedram, Mir Mohsen Kharazmi Univ Dept Elect & Comp Engn Fac Engn Tehran Iran

Decomposition of a matrix into low-rank matrices is a powerful tool for scientific computing and data analysis. The purpose is to obtain a low-rank matrix by decomposition of the original matrix into a product of smaller and lower-rank matrices or by randomly projecting the matrix down to a lower-dimensional space. Such decomposition requires less storage and computational burden. The focus of this paper is on randomized methods which try as much as possible to preserve the original matrix properties by applying the subspace sampling. In many applications, randomized algorithms in terms of accuracy, stability and speed are much better than the classical decomposition algorithms. In this study, we propose a sparse orthogonal transformation matrix to reduce the dimension of the data. The results show that compared with the most accurate methods, the transformation speed is much faster and can save a lot of memory in the case of huge matrices.

关键词： Matrix approximation Dimension reduction randomized algorithm Johnson-Lindenstrauss lemma Random matrix Column subset selection Big data

来源：评论

学校读者我要写书评

暂无评论

randomized block Krylov subspace methods for trace and log-determinant estimators

引用

BIT NUMERICAL MATHEMATICS 2021年第3期61卷 911-939页

作者： Li, Hanyu Zhu, Yuanyang Chongqing Univ Coll Math & Stat Chongqing 401331 Peoples R China

We present randomized algorithms based on block Krylov subspace methods for estimating the trace and log-determinant of Hermitian positive semi-definite matrices. Using the properties of Chebyshev polynomials and Gaussian random matrix, we provide the error analysis of the proposed estimators and obtain the expectation and concentration error bounds. These bounds improve the corresponding ones given in the literature. Numerical experiments are presented to illustrate the performance of the algorithms and to test the error bounds.

关键词： randomized algorithm Krylov subspace method Trace estimator Log-determinant estimator Chebyshev polynomials

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：