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

International Conference on Circuits, Systems, Communication and Information Technology Applications (CSCITA)

作者： Rangari, Jaypal D. Karmore, Swapnili P. GH Raisoni Coll Engn Dept CSE Nagpur Maharashtra India

ISBN: (纸本)9781479924943

Testing is the process of finding errors in a system or its component. It runs a system in order to find gaps or bugs. It also checks that system is fulfilling its requirement or not. During execution of software testing randomized algorithm is used to generate test cases. It generates random number of choices during test cases execution to produce a result. It selects test cases from the whole input set randomly. The process of test cases generation can be minimized using randomized algorithm. For generating test cases uses two types of randomized algorithm. We used different randomized algorithm on the basis of complexity of code. If the complexity is low then use Monte Carlo randomized algorithm because it has deterministic running time, but whose output may be incorrect with little probability. Las Vegas randomized algorithm is use for high complexity uses because it always gives the correct result. This algorithm compares the correlation between two far inputs and failure-causing inputs. It can avoid complex analysis and calculation of code. In this we focuses on various randomized testing algorithms and its working and functions. We present a method that improves performance random test generation by incorporating result obtained from executing test cases.

关键词： Testing random testing randomized algorithm performance of random testing software testing

来源：评论

学校读者我要写书评

暂无评论

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost 27

Correlation Clustering with Same-Cluster Queries Bounded by ...

引用

27th Annual European Symposium on algorithms (ESA)

作者： Saha, Barna Subramanian, Sanjay Univ Calif Berkeley Berkeley CA 94720 USA Allen Inst Artificial Intelligence Seattle WA USA

ISBN: (纸本)9783959771245

Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an oracle with full knowledge of an optimal clustering, and the algorithm can ask the oracle queries of the form, "Does the optimal clustering put vertices u and v in the same cluster?" Due to its simplicity, this querying model can easily be implemented in real crowd-sourcing platforms and has attracted a lot of recent work. In this paper, we study the popular correlation clustering problem (Bansal et al., 2002) under the same-cluster querying framework. Given a complete graph G = (V, E) with positive and negative edge labels, correlation clustering objective aims to compute a graph clustering that minimizes the total number of disagreements, that is the negative intra-cluster edges and positive inter-cluster edges. In a recent work, Ailon et al. (2018b) provided an approximation algorithm for correlation clustering that approximates the correlation clustering objective within (1 + epsilon) with O(k(14) log n log k /epsilon(6)) queries when the number of clusters, k, is fixed. For many applications, k is not fixed and can grow with vertical bar V vertical bar. Moreover, the dependency of k(1)4 on query complexity renders the algorithm impractical even for datasets with small values of k. In this paper, we take a different approach. Let C-OPT be the number of disagreements made by the optimal clustering. We present algorithms for correlation clustering whose error and query bounds are parameterized by C-OPT rather than by the number of clusters. Indeed, a good clustering must have small C-OPT. Specifically, we present an efficient algorithm that recovers an exact optimal clustering using at most 2C(OPT) queries and an efficient algorithm that outputs a 2-approximation using at most C-OPT queries. In addition, we show under a plausible complexity assumption

关键词： Clustering Approximation algorithm Crowdsourcing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast Optimal Subsampling Probability Approximation for Generalized Linear Models

引用

ECONOMETRICS AND STATISTICS 2024年 29卷 224-237页

作者： Lee, JooChul Schifano, Elizabeth D. Wang, HaiYing Univ Connecticut Dept Stat Storrs CT 06269 USA

For massive data, subsampling techniques are popular to mitigate computational burden by reducing the data size. In a subsampling approach, subsampling probabilities for each data point are specified to obtain an informative sub-data, and then estimates based on the sub-data are obtained to approximate estimates from the full data. Assigning subsampling probabilities based on minimization of the asymptotic mean squared error of the estimator from a general subsample (A-optimality criterion) is a popular approach, however, it is still computationally demanding to calculate the probabilities under this setting. To efficiently approximate the A-optimal subsampling probabilities for generalized linear models, randomized algorithms are proposed. To develop the algorithms, the Johnson-Lindenstrauss Transform and Subsampled randomized Hadamard Transform are used. Additionally, optimal subsampling probabilities are derived for the Gaussian linear model in the case where both the regression coefficients and dispersion parameter are of interest, and algorithms are developed to approximate the optimal subsampling probabilities. Simulation studies indicate that the estimators based on the developed algorithms have excellent performance for statistical inference and have substantial savings in computing time compared to the direct calculation of the A-optimal subsampling probabilities.(c) 2021 EcoSta Econometrics and Statistics. Published by Elsevier B.V. All rights reserved.

关键词： Generalized linear models Massive data Optimal subsampling randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True 2024

The Asymptotic Rank Conjecture and the Set Cover Conjecture ...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Bjoerklund, Andreas Kaski, Petteri IT Univ Copenhagen Copenhagen Denmark Aalto Univ Espoo Finland

ISBN: (纸本)9798400703836

Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specically, we study the so-called set cover conjecture, which states that for any epsilon > 0 there exists a positive integer constant k such that no algorithm solves the k-Set Cover problem in worst-case time O((2 - epsilon)(n) |F | poly(n)). The k-Set Cover problem asks, given as input an n-element universe U, a family F of size-at-most-k subsets of U, and a positive integer t, whether there is a subfamily of at most t sets in F whose union is U. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh in the monograph Parameterized algorithms [Springer, 2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlstrom [CCC 2012, ACM Trans. algorithms 2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS 2019], in this scenario we would also get an O((2 - delta)(n))-time randomized algorithm for some constant delta > 0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given n-vertex directed graph has a Hamiltonian cycle. At a fine-grained level, our results do not need the full strength of the asymptotic rank conjecture;it suffices that the conclusion of the conjecture holds approximately for a single 7 x 7 x 7 tensor.

关键词： asymptotic rank conjecture directed Hamiltonian cycle randomized algorithm set cover conjecture set partitioning three-way partitioning

来源：评论

学校读者我要写书评

暂无评论

Linear list-approximation for short programs (or the power of a few random bits)

Linear list-approximation for short programs (or the power o...

引用

IEEE 29th Conference on Computational Complexity (CCC)

作者： Bauwens, Bruno Zimand, Marius Univ Lorraine Nancy France Towson Univ Baltimore MD 21287 USA

ISBN: (纸本)9781479936267

A c-short program for a string x is a description of x of length at most C(x) + c, where C(x) is the Kolmogorov complexity of x. We show that there exists a randomized algorithm that constructs a list of n elements that contains a O(log n)-short program for x. We also show a polynomial-time randomized construction that achieves the same list size for O(log(2) n)-short programs. These results beat the lower bounds shown by Bauwens et al. [1] for deterministic constructions of such lists. We also prove tight lower bounds for the main parameters of our result. The constructions use only O(log n) (O(log(2) n) for the polynomial-time result) random bits. Thus using only few random bits it is possible to do tasks that cannot be done by any deterministic algorithm regardless of its running time.

关键词： Bipartite graph Complexity theory Entropy Polynomials Probabilistic logic Standards Turing machines Kolmogorov complexity approximation randomized algorithm Kolmogorov complexity randomized algorithms Probabilistic logic Automata theory-Turing machines Bipartite graph Complexity theory Polynomial entropy approximation Lower bound Drill bits nitrogen

来源：评论

学校读者我要写书评

暂无评论

Retrieving Routes of Interest Over Road Networks 17th

Retrieving Routes of Interest Over Road Networks

引用

17th International Conference on Web-Age Information Management (WAIM)

作者： Li, Wengen Cao, Jiannong Guan, Jihong Yiu, Man Lung Zhou, Shuigeng Hong Kong Polytech Univ Hong Kong Hong Kong Peoples R China Tongji Univ Shanghai Peoples R China Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9783319399379;9783319399362

In this paper, we propose route of interest (ROI) query which allows users to specify their interests with query keywords and returns a route such that (i) its distance is less than a distance threshold and (ii) its relevance to the query keywords is maximized. ROI query is particularly helpful for tourists and city explorers. For example, a tourist may wish to find a route from a scenic spot to her hotel to cover many artware shops. It is challenging to efficiently answer ROI query due to its NP-hard complexity. Novelly, we propose an adaptive route sampling framework that adaptively computes a route according to a given response time, and gradually improve the quality of the route with time. Moreover, we design a suite of route sampling techniques under this framework. Experiments on real data suggest that our proposed solution can return high quality routes within a short response time.

关键词： Route of interest Route sampling randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Constant-Factor Approximation algorithm for Planar Visibility Counting Problem 22nd

An Improved Constant-Factor Approximation Algorithm for Plan...

引用

22nd International Computing and Combinatorics Conference (COCOON)

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Sharif Univ Technol Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran

ISBN: (纸本)9783319426341;9783319426334

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can trivially be solved in logarithmic query time using O(n(4)) preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a trade-off between the space and the query time. They answer any query in O epsilon(n (1-alpha)) with O epsilon (n(2+2 alpha)) of preprocessing time and space, where alpha is a constant 0 <= alpha <= 1, epsilon > 0 is another constant that can be made arbitrarily small, and O epsilon(f(n)) = O(f( n)n(epsilon)). In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants 0 <= beta <= 2/3 and 0 < delta < 1, the expected preprocessing time, the expected space, and the query time of our algorithm are O( n(4-3 beta) log n), O(n(4-3 beta)), and O(1/delta(3)n(beta) log n), respectively. The algorithm computes the number of visible segments from p, or mp, exactly if m(p) <= (1)/(3)(delta)n(beta) log ***, it computes a ( 1+ delta)-approximation m'(p) with the probability of at least 1- 1/log n, where m(p) <= m'(p) <= ( 1 + delta) m(p).

关键词： Computational geometry Visibility randomized algorithm Approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

The linear voting model 43

The linear voting model

引用

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016

作者： Cooper, Colin Rivera, Nicolas Department of Informatics King's College London London United Kingdom

ISBN: (纸本)9783959770132

We study voting models on graphs. In the beginning, the vertices of a given graph have some initial opinion. Over time, the opinions on the vertices change by interactions between graph neighbours. Under suitable conditions the system evolves to a state in which all vertices have the same opinion. In this work, we consider a new model of voting, called the Linear Voting Model. This model can be seen as a generalization of several models of voting, including among others, pull voting and push voting. One advantage of our model is that, even though it is very general, it has a rich structure making the analysis tractable. In particular we are able to solve the basic question about voting, the probability that certain opinion wins the poll, and furthermore, given appropriate conditions, we are able to bound the expected time until some opinion wins. © Colin Cooper and Nicolas Rivera.

关键词： Interacting particles Probabilistic voting randomized algorithm Voter model

来源：评论

学校读者我要写书评

暂无评论

Computational Methods For Functional Motif Identification and Approximate Dimension Reduction in Genomic Data

Computational Methods For Functional Motif Identification an...

引用

作者： Georgiev, Stoyan Duke University

学位级别：Ph.D.

Uncovering the DNA regulatory logic in complex organisms has been one of the important goals of modern biology in the post-genomic era. The sequencing of multiple genomes in combination with the advent of DNA microarrays and, more recently, of massively parallel high-throughput sequencing technologies has made possible the adoption of a global perspective to the inference of the regulatory rules governing the context-specific interpretation of the genetic code that complements the more focused classical experimental approaches. Extracting useful information and managing the complexity resulting from the sheer volume and the high-dimensionality of the data produced by these genomic assays has emerged as a major challenge which we attempt to address in this work by developing computational methods and tools, specifically designed for the study of the gene regulatory processes in this new global genomic context. First, we focus on the genome-wide discovery of physical interactions between regulatory sequence regions and their cognate proteins at both the DNA and RNA level. We present a motif analysis framework that leverages the genome-wide evidence for sequence-specific interactions between trans-acting factors and their preferred cis-acting regulatory regions. The utility of the proposed framework is demonstarted on DNA and RNA cross-linking high-throughput data. A second goal of this thesis is the development of scalable approaches to dimension reduction based on spectral decomposition and their application to the study of population structure in massive high-dimensional genetic data sets. We have developed computational tools and have performed theoretical and empirical analyses of their statistical properties with particular emphasis on the analysis of the individual genetic variation measured by Single Nucleotide Polymorphism (SNP) microrarrays.

关键词： Bioinformatics binding site chip-seq dimension reduction population structure randomized algorithm transcription factor

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：