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

2nd International Conference on Computer Engineering and Applications

作者： Nasien, Dewi Haron, Habibollah Yuhaniz, Siti Sophiayati Univ Teknol Malaysia Dept Modeling & Ind Comp Johor Baharu Malaysia

ISBN: (纸本)9780769539829

This paper proposes a recognition model for English handwritten (lowercase, uppercase and letter) character recognition that uses Freeman chain code (FCC) as the representation technique of an image character. Chain code representation gives the boundary of a character image in which the codes represent the direction of where is the location of the next pixel. An FCC method that uses 8-neighbourhood that starts from direction labelled as 1 to 8 is used. randomized algorithm is used to generate the FCC. After that, features vector is built. The criteria of features to input the classification is the chain code that converted to 64 features. Support vector machine (SVM) is chosen for the classification step. NIST Databases are used as the data in the experiment. Our test results show that by applying the proposed model, we reached a relatively high accuracy for the problem of English handwritten recognition.

关键词： Freeman chain code (FCC) Heuristic method randomized algorithm features vector Support vector machine (SVM)

来源：评论

学校读者我要写书评

暂无评论

Replacement Paths via Fast Matrix Multiplication

Replacement Paths via Fast Matrix Multiplication

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Weimann, Oren Yuster, Raphael Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Haifa Dept Math Haifa Israel

ISBN: (纸本)9780769542447

Let G be a directed edge-weighted graph and let P be a shortest path from s to t in G. The replacement paths problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem removing each edge e on P one at a time and computing the shortest s-to-t path each time - is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related shortest paths problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths between -M and M, we give a randomized algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.

关键词： approximation algorithm data structure directed edge-weighted graph directed graphs distance sensitivity oracle fast matrix multiplication matrix algebra randomised algorithms randomized algorithm replacement path sub-quadratic time

来源：评论

学校读者我要写书评

暂无评论

Discrete Load Balancing is (almost) as Easy as Continuous Load Balancing

Discrete Load Balancing is (almost) as Easy as Continuous Lo...

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Elsaesser, Robert Sauerwald, Thomas Univ Freiburg Inst Comp Sci D-79110 Freiburg Germany

ISBN: (纸本)9781605588889

We consider the problem of diffusion-based load balancing on a distributed network with n processors. If the load is arbitrarily divisible, then the convergence is fairly well captured in terms of the second largest eigenvalue of the diffusion matrix. As for many applications load can not be arbitrarily divided, we consider a model where load consists of indivisible, unit-size tokens. Quantifying by how much this integrality assumption worsens the efficiency of load balancing algorithms is a natural question which has been posed by many authors [9, 15, 16, 19, 6, 17]. In this paper we show essentially that discrete load balancing is almost as easy as continuous load balancing. More precisely, we present a fully distributed, randomized algorithm for discrete load balancing that balances the load up to an additive constant error on any graph in time O(log(Kn)/(1-lambda(2))), where K is the initial imbalance and lambda(2) is the second largest eigenvalue of the diffusion matrix. This improves and tightens a result of Elsasser, Monien, Schamberger (2006) who proved a runtime bound of O((log(K) + (log n)(2))/(1-lambda(2))). We also develop a load balancing algorithm based on routing that achieves a runtime of O(D . log n), where D is the diameter of the graph.

关键词： Load Balancing randomized algorithm Random Walks

来源：评论

学校读者我要写书评

暂无评论

On the Number of Solutions of the Equation Rx(2)

引用

SANKHYA-SERIES A-MATHEMATICAL STATISTICS AND PROBABILITY 2010年第1期72卷 226-236页

作者： Barua, Rana Jhanwar, Mahabir P. Indian Stat Inst Stat Math Unit 203 BT Rd Kolkata 700108 India

We find by elementary methods the number of solutions of the equation RX2 + SY2 = 1 (mod N), where N is an RSA composite and R, S are given integers coprime to N. When S (or R) is a square modulo N and its square root is known, our approach gives a very simple randomized algorithm for finding a solution. We also find the number of solutions in terms of Legendre and Jacobi symbols.

关键词： Congruences number of solutions randomized algorithm Jacobi and Legendre symbols

来源：评论

学校读者我要写书评

暂无评论

Theoretical and experimental analysis of a randomized algorithm for Sparse Fourier transform analysis

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2006年第2期211卷 572-595页

作者： Zou, J Gilbert, A Strauss, M Daubechies, I Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Princeton Univ Dept Math Princeton NJ 08544 USA

We analyze a sublinear RAlSFA (randomized algorithm for Sparse Fourier analysis) that finds a near-optimal B-term, Sparse representation R for a given discrete signal S of length N, in time and space poly(B, log(N)), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost poly(log(N)) should be compared with the superlinear Omega(N logN) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RAlSFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RAlSFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RAlSFA constructs, with probability at least 1 - delta, a near-optimal B-term representation R in time poly(B) log(N) log(1/delta)/is an element of(2) log(M) such that vertical bar vertical bar S - R vertical bar vertical bar(2)(2) <= (1 + is an element of) vertical bar vertical bar S - R(opt)vertical bar vertical bar(2)(2). Furthermore, this RAlSFA implementation already beats the FFTW for not unreasonably large N. We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at N similar or equal to 70, 000 in one dimension, and at N similar or equal to 900 for data on a N x N grid in two dimensions for small B signals where there is noise. (c) 2005 Elsevier Inc. All rights reserved.

关键词： RAlSFA sparse Fourier representation fast Fourier transform sublinear algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Design of heat exchanger networks using randomized algorithm

引用

COMPUTERS & CHEMICAL ENGINEERING 2006年第6-7期30卷 1046-1053页

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

A randomized algorithm with stream splitting for design of heat exchanger networks is presented in this work. The algorithm has provisions for splitting any one of the process streams. We have studied three benchmark problems taken from literature. The results obtained from these studies clearly indicate the strength of the randomization method in finding a cost-effective network. This random search method can find better networks, which are sometimes unnoticed by other optimization techniques. The simplicity of this method as well as the networks obtained is an additional attractive feature, which should encourage the designers to use it. From the results of this study, randomization is recommended as a reliable check for designing heat exchanger networks. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： heat exchanger network design minimum cost network randomized algorithm random search stream splitting

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Discrete Optimization

引用

丛书名： Zurich lectures in advanced mathematics

2010年

作者： Shmuel Onn

ISBN: (数字)9783037195932

ISBN: (纸本)9783037190937

This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases. The monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.

关键词： Integer programming combinatorial optimization optimization linear programming stochastic programming randomized algorithm approximation algorithm polynomial time transportation problem multi index transportation problem transshipment problem multicommodity flow congestion game spanning tree matroid submodular function matching partitioning clustering polytope zonotope edge direction totally unimodular matrix test set Graver base contingency table statistical table multiway table disclosure control data security privacy algebraic statistics experimental design Frobenius number Grobner base Hilbert scheme zero-dimensional ideal

来源：评论

学校读者我要写书评

暂无评论

On the runtime and robustness of randomized broadcasting

引用

THEORETICAL COMPUTER SCIENCE 2009年第36期410卷 3414-3427页

作者： Elsaesser, R. Sauerwald, T. Univ Paderborn Inst Comp Sci D-33102 Paderborn Germany

In this paper, we study the following randomized broadcasting protocol. At some time t an information r is placed at one of the nodes of a graph. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of r to it. We begin by developing tight lower and upper bounds on the runtime of the algorithm described above. First, it is shown that on Delta-regular graphs this algorithm requires at least log(2-1/Delta) n + log((Delta/Delta-1)Delta) n - o(log n) approximate to 1.69 log(2) n rounds to inform all n nodes. Together with a result of Pittel [B. Pittel, On spreading a rumor, SIAM journal on Applied Mathematics, 47 (1) (1987) 213-223] this bound implies that the algorithm has the best performance on complete graphs among all regular graphs. For general graphs, we prove a slightly weaker lower bound of log(2-1/Delta) n+log4 n-o(log n) approximate to 1.5 log(2) n, where Delta denotes the maximum degree of G. We also prove two general upper bounds, (1 + o(1))n ln n and O(n Delta/delta), respectively, where delta denotes the minimum degree. The second part of this paper is devoted to the analysis of fault-tolerance. We show that if the informed nodes are allowed to fail in some step with probability 1 - p, then the broadcasting time increases by at most a factor 6/p. As a by-product, we determine the performance of agent based broadcasting in certain graphs and obtain bounds for the runtime of randomized broadcasting on Cartesian products of graphs. (C) 2008 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Distributed computing

来源：评论

学校读者我要写书评

暂无评论

randomized approximation of Sobolev embeddings, III

引用

JOURNAL OF COMPLEXITY 2009年第5期25卷 473-507页

作者： Heinrich, Stefan Univ Kaiserslautern Fachbereich Informat D-67653 Kaiserslautern Germany

We continue the study of randomized approximation of embeddings between Sobolev spaces on the basis of function values. The source space is a Sobolev space with nonnegative smoothness order;the target space has negative smoothness order. The optimal order of approximation (in some cases only up to logarithmic factors) is determined. Extensions to Besov and Bessel potential spaces are given and a problem recently posed by Novak and Wozniakowski is partially solved. The results are applied to the complexity analysis of weak solution of elliptic PDE. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Approximation randomized algorithm Sobolev space Sampling Lower bounds

来源：评论

学校读者我要写书评

暂无评论

randomized approximation of Sobolev embeddings, II

引用

JOURNAL OF COMPLEXITY 2009年第5期25卷 455-472页

作者： Heinrich, Stefan Univ Kaiserslautern Fachbereich Informat D-67653 Kaiserslautern Germany

We Study the approximation of Sobolev embeddings by linear randomized algorithms based on function values. Both the source and the target space are Sobolev spaces of non-negative smoothness order, defined on a bounded Lipschitz domain. The optimal order of convergence is determined. We also study the deterministic setting. Using interpolation, we extend the results to other classes of function spaces. In this context a problem posed by Novak and Wozniakowski is solved. Finally, we present an application to the complexity of general elliptic PDE. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Approximation randomized algorithm Sobolev space Sampling Lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：