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

On the Probability of Generating a Primitive Matrix

Journal of Systems Science & Complexity 2024年第4期37卷 1755-1771页

作者： CHEN Jingwei FENG Yong LIU Yang WU Wenyuan Chongqing Key Laboratory of Automated Reasoning and Cognition Chongqing Institute of Green and Intelligent TechnologyChinese Academy of SciencesChongqing 400714China Chongqing College University of Chinese Academy of SciencesChongqing 400714China Key Laboratory of Advanced Manufacturing Technology of Ministry of Education Guizhou UniversityyGuiyang 550025China Information Science and Engineering Chongqing Jiaotong UniversityChongqing 400074China

Given a k×n integer primitive matrix A(i.e.,a matrix can be extended to an n×n unimodular matrix over the integers)with the maximal absolute value of entries‖A‖bounded by an integer λ from above,the authors study the probability that the m×n matrix extended from A by appending other m-k row vectors of dimension n with entries chosen randomly and independently from the uniform distribution over{0,1,…,λ-1}is still *** authors present a complete and rigorous proof of a lower bound on the probability,which is at least a constant for fixed m in the range[k+1,n-4].As an application,the authors prove that there exists a fast Las Vegas algorithm that completes a k×n primitive matrix A to an n×n unimodular matrix within expected O(n^(ω)log‖A‖)bit operations,where O is big-O but without log factors,ω is the exponent on the arithmetic operations of matrix multiplication.

关键词： Integer matrix matrix completion probabilistic algorithm unimodular matrix

来源：评论

学校读者我要写书评

暂无评论

Fishman's sampling plan for computing network reliability

引用

IEEE TRANSACTIONS ON RELIABILITY 2001年第1期50卷 41-46页

作者： Manzi, E Labbé, M Latouche, G Maffioli, F Free Univ Brussels Inst Stat & Rech Operationnelle B-1050 Brussels Belgium Free Univ Brussels Dept Informat B-1050 Brussels Belgium Politecn Milan Dipartimento Elettron & Informat I-20133 Milan Italy

This paper analyzes a sampling method proposed by Fishman [4] for computing the 2-terminal and global reliability of a network. It describes, completely and clearly, the sampling algorithm, and computation experiments on networks corresponding to a real situation as well as examples from the literature. A communication network is modeled by an undirected graph as a function of the set of vertices (the network nodes) and the set of edges (the links connecting pairs of vertices), Each edge is in 1 of 2 states (operational and failed), Failures are assumed to be statistically independent, A network is connected iff the set of edges that are operational, forms a spanning connected subgraph (a, subgraph containing at least 1 operational path between any 2 vertices), The problems of computing: 1) the 2-terminal network reliability (probability that between 2 given vertices there exists at least 1 operational path) and 2) the global network reliability (probability that the network is connected), are treated. For problem 1, Fishman [4] proposed a Monte Carlo sampling plan, which uses lower and upper bounds to increase its accuracy and efficiency, Although the ideas in [4] are useful, the paper lacks clarity, This paper provides i) a detailed, clear exposition of the Fishman method, ii) a complete description of the corresponding algorithm, iii) its extension for computing global reliability (problem 2), and iv) computational experiments on networks both new and in the literature. A Monte Carlo approach for these problems is fully justified by looking at their computational complexity. The exact computation of the network reliability (either 2-terminal or global) is a #P-complete problem (a problem harder than the whole hierarchy of NP-hard problems). If one looks for efficient algorithms, one must settle for approximations obtained by a heuristic procedure.

关键词： Monte Carlo sampling network reliability probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

PACKING ITEMS FROM A TRIANGULAR DISTRIBUTION

引用

INFORMATION PROCESSING LETTERS 1987年第6期25卷 351-361页

作者： KRAUSE, K LARMORE, LL VOLPER, DJ Dep. Inf. and Comp. Sci. Univ. California Irvine CA 92717 USA

The authors consider the problem of packing n items, which are drawn according to a probability distribution whose density function is triangular in shape, into bins of unit capacity. For triangles which represent density functions whose expectation is 1/p for p = 3, 4, 5,..., they give a packing strategy for which the ratio of the number of bins used in the packing to the expected total size of the items asymptotically approaches 1.

关键词： Bin-packing probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements

引用

PROBLEMS OF INFORMATION TRANSMISSION 2023年第1期59卷 57-62页

作者： Vyalyi, M. N. Russian Acad Sci Fed Res Ctr Comp Sci & Control Moscow Russia Natl Res Univ Higher Sch Econ Moscow Russia Moscow Inst Phys & Technol Moscow Russia

We construct a probabilistic polynomial algorithm for testing the satisfiability of algebraic formulas of depth 3 over the two-element field, with addition as the top operation in the formulas. An algorithm with the same characteristics exists for the problem of testing whether a polynomial given by formulas of this type is identically zero (PIT problem). However, these problems and algorithms for their solution are essentially different. The probabilistic algorithm for the PIT problem is based on the Schwartz-Zippel lemma, whereas the satisfiability testing algorithm proposed in this paper is based on the Valiant-Vazirani lemma.

关键词： satisfiability of Boolean formulas probabilistic algorithm algebraic formulas

来源：评论

学校读者我要写书评

暂无评论

Finding pathway structures in protein interaction networks

引用

algorithmICA 2007年第4期48卷 363-374页

作者： Lu, Songjian Zhang, Fenghui Chen, Jianer Sze, Sing-Hoi Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Texas A&M Univ Dept Biochem & Biophys College Stn TX 77843 USA

The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in O(4(k)n(2t) k(t+ log( t+ 1)+ 2.92)t(2)) time and O(n(t) k log k + m) space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices ( i. e., " width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity 4(k)n(O(1)) is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.

关键词： probabilistic algorithm pathway structure protein interaction network

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF LINEAR-MAPS FOR ERROR CORRECTIVE DIMENSIONALITY REDUCTION OF BINARY TEMPLATES

引用

PATTERN RECOGNITION 1988年第4期21卷 381-392页

作者： KUNDU, S INDIAN STAT INST ELECTR & COMMUN SCI UNITCALCUTTA 700035W BENGALINDIA

Binary templates are optimally encoded in a reduced dimension by a proposed class of linear maps that preserves the local neighbourhood and a prescribed minimum distance between the prototypes to a workable extent. This in effect generates a nearness criterion suitable for template matching with a level of error correcting capability in the reduced space while requiring only a fraction of memory storage space and boolean operations that would have been required otherwise. Characters and symbols may now be designed with reference to separation and shape but with a comparative freedom from the constraint of dimension, while a volume of such data can be transmitted with the speed and bandwidth of the encoded data. Some of the principal problems associated with template matching are thus overcome. Here all the necessary operations are performed in the finite field GF(2) and the methodology developed can be implemented in a microcomputer with improved system performance and economy.

关键词： Algebraic algorithm Dimensionality reduction Error correction Linear mapping Minimum distance encoding Neighbourhood preserving transformation Optimal encoding probabilistic algorithm Perfect hash function Template stylization

来源：评论

学校读者我要写书评

暂无评论

Binary Search in Graphs Revisited

引用

algorithmICA 2019年第5期81卷 1757-1780页

作者： Deligkas, Argyrios Mertzios, George B. Spirakis, Paul G. Technion Fac Ind Engn & Management Haifa Israel Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Patras Dept Comp Sci Patras Greece

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519-532, 2016) to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates' set for the target, while each query asks an appropriately chosen vertex-the "median"-which minimises a potential Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Gamma that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential Gamma that allows querying approximate medians.

关键词： Binary search Graph Approximate query probabilistic algorithm Lower bound

来源：评论

学校读者我要写书评

暂无评论

2 APPLICATIONS OF INDUCTIVE COUNTING FOR COMPLEMENTATION PROBLEMS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1989年第3期18卷 559-578页; 作者： BORODIN, A COOK, SA DYMOND, PW RUZZO, WL TOMPA, M UNIV CALIF SAN DIEGO DEPT COMP SCI & ENGNC-014LA JOLLACA 92093 UNIV WASHINGTON DEPT COMP SCIFR-35SEATTLEWA 98195 IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598; Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] that nondeterministic space-bounded... 详细信息; Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] that nondeterministic space-bounded complexity classes are closed under complementation, two further applications of the inductive counting technique are developed. First, an errorless probabilistic algorithm for the undirected graph s-t connectivity problem that runs in $O (\log n)$; 来源：评论; 学校读者我要写书评

暂无评论

Exploiting partial knowledge of satisfying assignments

引用

DISCRETE APPLIED MATHEMATICS 2007年第12期155卷 1596-1603页

作者： Iwama, Kazuo Tamaki, Suguru Kyoto Univ Sch Informat Kyoto 6068501 Japan

Recently Schoning has shown that a simple local-search algorithm for 3SAT achieves the currently best upper bound, i.e., an expected time of 1.334(n). In this paper, we show that this algorithm can be modified to run much faster if there is some kind of imbalance in satisfying assignments and we have a (partial) knowledge about that. Especially if a satisfying assignment has imbalanced 0's and 1's, i.e., p(1)n 1's and (1-p(1))n 0's, then we can find a solution in time 1.260(n) when p(1) = 71 and 1.072(n) when p(1) = 0.1. Such an imbalance often exists in SAT instances reduced from other problems. As a concrete example, we investigate a reduction from 3DM and show our new approach is nontrivially faster than its direct algorithms. Preliminary experimental results are also given. (c) 2006 Elsevier B.V. All rights reserved.

关键词： CNF satisfiability probabilistic algorithm NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

Average performance of greedy heuristics for the integer knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2004年第1期154卷 36-45页

作者： Kohli, R Krishnamurti, R Mirchandani, P Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Columbia Univ Grad Sch Business New York NY 10027 USA Univ Pittsburgh Katz Grad Sch Business Pittsburgh PA 15260 USA

This paper derives a lower bound on the average performance of a total-value greedy heuristic for the integer knapsack problem. This heuristic selects items in order of their maximum possible contribution to the solution value at each stage. We show that, as for the worst-case bound, the average performance bound for the total-value heuristic dominates the corresponding bound for the density-ordered greedy heuristic. (C) 2002 Elsevier B.V. All rights reserved.

关键词： heuristics combinatorial optimization integer programming knapsack probabilistic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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