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

Efficient sample sort and the average case analysis of PEsort

THEORETICAL COMPUTER SCIENCE 2006年第1-3期369卷 44-66页

作者： Chen, Jing-Chao DongHua Univ Sch Informat Shanghai 200051 Peoples R China

The purpose of the paper is twofold. First, we want to search for a more efficient sample sort. Secondly, by analyzing a variant of Samplesort, we want to settle an open problem: the average case analysis of Proportion Extend Sort (PEsort for short). An efficient variant of Samplesort given in the paper is called full sample sort. This algorithm is simple. It has a shorter object code and is almost as fast as PEsort. Theoretically, we show that full sample sort with a linear sampling size performs at most n log n + O(n) comparisons and O(n log n) exchanges on the average, but O(n log(2) n) comparisons in the worst case. This is an improvement on the original Samplesort by Frazer and McKellar, which requires n log n + O(n log log n) comparisons on the average and O(n(2)) comparisons in the worst case. On the other hand, we use the same analyzing approach to show that PEsort, with any p > 0, performs also at most n log n + O (n) comparisons on the average. Notice, Cole and Kandathil analyzed only the case p = 1 of PEsort. For any p > 0, they did not. Namely, their approach is suitable only for a special case such as p = 1, while our approach is suitable for the generalized case. (c) 2006 Elsevier B.V. All rights reserved.

关键词： sorting samplesort complexity of algorithms master theorem quicksort proportion extend sort

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm to Solve Delay Vandermonde Systems in Phased-Array Digital Receivers

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2021年第4期57卷 2288-2297页

作者： Perera, Sirani M. Madanayake, Arjuna Ogle, Austin Silverio, Daniel Huang, Jacky Qi Embry Riddle Aeronaut Univ Dept Math Daytona Beach FL 32703 USA Florida Int Univ Dept Elect & Comp Engn Miami FL 33199 USA Embry Riddle Aeronaut Univ Daytona Beach FL 32703 USA

Phased-array multibeam RF beamformers require calibration of receivers used in an array of elements before the signals can be applied to an analog beamforming network. This article presents a fast O(n(2)) algorithm for solving linear systems having a delay Vandermonde matrix (DVM) for the analog beamforming matrix. The structure of the DVM enables to obtain a fast algorithm to efficiently reverse multibeams at the DVM output such that calibration of the input low noise amplifiers can be achieved. The arithmetic complexity of the proposed DVM system solving algorithm is preferable over the standard matrix inversion consuming O(n(3)) operations. Numerical experiments are presented for forward accuracy of the proposed algorithm computed at the calibration frequency. Moreover, numerical results are shown to compare the order of the arithmetic complexity and the execution time of the proposed algorithm. Signal flow graphs are presented for four- and eight-element multibeam phased arrays.

关键词： Transmission line matrix methods Calibration Array signal processing Delays Software algorithms Software Signal to noise ratio Antenna arrays complexity of algorithms discrete Fourier transform (DFT) fast algorithms matrix inversion millimeter wave communication performance of algorithms phased-array radar sparse matrices

来源：评论

学校读者我要写书评

暂无评论

Hamiltonian problems in directed graphs with simple row patterns

引用

THEORETICAL COMPUTER SCIENCE 2022年 916卷 70-85页

作者： Rusu, Irena Univ Nantes UMR 6004 LS2N 2 rue HoussiniereBP 92208 F-44322 Nantes France

We define a row pattern of a matrix as a model (or a condition) to be satisfied by each row of the matrix, independently of the other rows. When applied to adjacency matrices of digraphs, a row pattern allows to define a class of digraphs characterized by a local condition on the out-neighborhood of each vertex, once an appropriate linear ordering of the vertices has been found. We show that the Hamiltonian Cycle and Hamiltonian Path problems are NP-complete on digraphs with simple row patterns, namely C1P-digraphs (where the row pattern describes the consecutive ones property), 2-out-regular digraphs (where each row contains exactly two values 1) and sym-digraphs (where the 1s in each row are symmetric with respect to the main diagonal, as soon as the row contains at least two 1s). Classes with simple row patterns thus show a real structural complexity, despite their simple definitions. Moreover, they raise interesting class recognition problems. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Hamiltonian problems complexity of algorithms Linear ordering of the vertices Consecutive ones property

来源：评论

学校读者我要写书评

暂无评论

AN INTERIOR POINT ALGORITHM OF O(ROOT-M-VERTICAL-BAR-LN-EPSILON-VERTICAL-BAR) ITERATIONS FOR C1-CONVEX PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1992年第2期57卷 239-257页

作者： SUN, J QI, LQ UNIV NEW S WALES SCH MATH KENSINGTON NSW 2033 AUSTRALIA

We present a theoretical result on a Path-following algorithm for convex programs. The algorithm employs a nonsmooth Newton subroutine. It starts from a near center of a restricted constraint set, performs a partial nonsmooth Newton step in each iteration, and converges to a Point whose cost is within epsilon accuracy of the optimal cost in O(square-root m\ ln epsilon\) iterations, where m is the number of constraints in the problem. Unlike other interior point methods, the analyzed algorithm only requires a first-order Lipschitzian condition and a generalized Hessian similarity condition on objective and constraint functions. Therefore, our result indicates the theoretical feasibility of applying interior point methods to certain C1-optimization problems instead of C2-problems. Since the complexity bound is unchanged compared with similar algorithms for C2-convex programming, the result shows that the smoothness of functions may not be a factor affecting the complexity of interior point methods.

关键词： complexity of algorithms CONVERGENCE ANALYSIS INTERIOR POINT algorithms NEWTON METHODS

来源：评论

学校读者我要写书评

暂无评论

Approximate Boyer-Moore String Matching for Small Alphabets

引用

ALGORITHMICA 2010年第3期58卷 591-609页

作者： Salmela, Leena Tarhio, Jorma Kalsi, Petri Helsinki Univ Technol Dept Comp Sci & Engn Espoo 02015 Finland

Recently a new variation of approximate Boyer-Moore string matching was presented for the k-mismatch problem. The variation, called FAAST, is specifically tuned for small alphabets. We further improve this algorithm gaining speedups in both preprocessing and searching. We also present three variations of the algorithm for the k-difference problem. We show that the searching time of the algorithms is average-optimal and the preprocessing also has a lower time complexity than FAAST. Our experiments show that our algorithm for the k-mismatch problem is about 30% faster than FAAST and the new algorithms compare well against other state-of-the-art algorithms for approximate string matching.

关键词： Approximate string matching Edit distance Hamming distance complexity of algorithms Biological sequences

来源：评论

学校读者我要写书评

暂无评论

Showcasing straight-line programs with memory via matrix Bruhat decomposition

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2024年第7期34卷 1059-1090页

作者： Niemeyer, Alice C. Popiel, Tomasz Praeger, Cheryl E. Rademacher, Daniel Rhein Westfal TH Aachen Chair Algebra & Representat Theory Pontdriesch 10-16 D-52062 Aachen Germany Monash Univ Sch Math 9 Rainforest Walk Clayton Vic 3800 Australia Univ Western Australia Ctr Math Symmetry & Computat 35 Stirling Highway Crawley WA 6009 Australia

We suggest that straight-line programs designed for algebraic computations should be accompanied by a comprehensive complexity analysis that takes into account both the number of fundamental algebraic operations needed, as well as memory requirements arising during evaluation. We introduce an approach for formalizing this idea and, as illustration, construct and analyze straight-line programs for the Bruhat decomposition of d x d matrices with determinant 1 over a finite field of order q that have length O(d2log(q)) and require storing only O(log(q)) matrices during evaluation.

关键词： Straight-Line program complexity of algorithms Bruhat decomposition memory complexity

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL ATTRIBUTE RANKING IN MULTIPLE ATTRIBUTE TREE

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1987年第1期21卷 31-42页

作者： RAO, SVN IYENGAR, SS Department of Computer Science Coates Hall Louisiana State University Baton Rouge LA 70803 United States

In a Multiple Attribute Tree (MAT) based data organization, the average case response to a specific range query depends on the structural properties of MAT. These structural properties depend very much on the interrelationships among the data elements. Efficiency in searching can be achieved by exploiting the data properties in the construction of MAT. The order or ranking of attributes is a key factor in deciding the profile of the MAT for given data. In this paper, we estimate the average cost of a range query in MAT based data organization. We then prove that the average performance can be improved by ranking the attributes in such a way that the average size of the filial sets decreases towards the lower levels of the tree structure.

关键词： Multiple attribute tree range search complexity of algorithms E.1 Data Structures F.2 Data Storage Representations

来源：评论

学校读者我要写书评

暂无评论

SOME RECENT RESULTS IN HEURISTIC-SEARCH THEORY

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1984年第1期6卷 1-13页

作者： PEARL, J UNIV CALIF LOS ANGELES DEPT COMP SCICOGNIT SCI LABLOS ANGELESCA 90024

The paper summarizes recent analytical investigations of the mathematical properties of heuristics and their influence on the performance of common search techniques. The results are reported without proofs together with discussions of motivations and interpretations. The highlights include the following: the optimality of A*; relations between the precision of the heuristic estimates and the average complexity of the search; comparisons of the average complexities of A* and BACKTRACKING; procedures for comparing and combining nonadmissible heuristic functions; the influence of the weight w (in f = (l - w) g + wh) on the complexity of A*; the pruning power of alphabeta, SSS*, and SCOUT; the effect of successor ordering on search complexity, and the effect of search depth of the quality of decisions in game-playing.","doi":"10.1109/TPAMI.1984.4767470","publicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","startPage":"1","endPage":"13","rightsLink":"http://***/AppDispatchServlet?publisherName=ieee&publication=0162-8828&title=Some+Recent+Results+in+Heuristic+Search+Theory&isbn=&publicationDate=Jan.+1984&author=Judea+Pearl&ContentID=10.1109/TPAMI.1984.4767470&orderBeanReset=true&startPage=1&endPage=13&volumeNum=PAMI-6&issueNum=1","displayPublicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","pdfPath":"/iel5/34/4767466/***","keywords":[{"type":"IEEE Keywords","kwd":["Performance analysis","Testing","Mathematical model","Search methods","Heuristic algorithms","Laboratories","Computer science","Natural languages","Distributed computing","Probability distribution"]},{"type":"Author Keywords ","kwd":["heuristic search","Combinatorial algorithms","complexity of algorithms","game-searching programs"]}],"allowComments":false,"pubLink":"/xpl/***?punumber=34","issueLink":"/xpl/***?isnumber=4767466","standardTitle":"Some Recent Results in Heuristic Search Theory

关键词： Performance analysis Testing Mathematical model Search methods Heuristic algorithms Laboratories Computer science Natural languages Distributed computing Probability distribution Author Keywords heuristic search Combinatorial algorithms complexity of algorithms game-searching programs

来源：评论

学校读者我要写书评

暂无评论

Monotone bipartitioning problem in a planar point set with applications to VLSI

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2002年第2期7卷 231-248页

作者： Dasgupta, P Pan, PC Nandy, SC Bhattacharya, BB Indian Inst Management Kolkata 700027 W Bengal India Aplus Design Technol Inc Los Angeles CA 90024 USA Indian Stat Inst Kolkata 700108 W Bengal India Univ Nebraska Dept Comp Sci & Engn Lincoln NE 68588 USA

A new problem called monotone bipartitioning of a planar point set is identified which is found to be useful in VLSI layout design. Let F denote a rectangular floor containing a set A of n points. The portion of a straight line formed by two points from the set A is called a line segment. A monotone increasing path (MP) in F is a connected and ordered sequence of line segments from the bottom-left corner of F to its top-right corner, such that the slope of each line segment is nonnegative, and each pair of consecutive line segments share a common point of A. An MP is said to be maximal (MMP) if no other point in A can be included in it preserving monotonicity. Let A(L) denote the subset of A corresponding to the end points of the line segments in an MMP, L. The path L partitions the set of points A n A L into two subsets lying on its two sides. The objective of monotone bipartitioning is to find an MMP L, such that the difference in the number of points in these two subsets is minimum. This problem can be formulated as finding a path between two designated vertices of an edge-weighted digraph (the weight of an edge being an integer lying in the range [ - n, n]), for which the absolute value of the algebraic sum of weights is minimized. An O( n x e) time algorithm is proposed for this problem, where e denotes the number of edges of the graph determined from the geometry of the point set. The monotone bipartitioning problem has various applications to image processing, facility location, and plant layout problems. A related problem arises while partitioning a VLSI floorplan. Given a floorplan with n rectangular blocks, the goal is to find a monotone staircase channel from one corner of the floor to its diagonally opposite corner such that the difference in the numbers of blocks lying on its two sides is minimum. The problem is referred to as the staircase bipartitioning problem. The proposed algorithm for a point set can be directly used to solve this problem in O(n(2

关键词： complexity of algorithms floorplanning partitioning routing very large scale integration (VLSI)

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

引用

ANNALS OF OPERATIONS RESEARCH 2014年第1期223卷 155-171页

作者： Dourado, Mitre C. Oliveira, Rodolfo A. Protti, Fabio Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Fed Fluminense Niteroi RJ Brazil

For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Steiner -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner -tree in polynomial time, our algorithm enumerates the remaining trees with delay (where ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966-984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given and a vertex , is in a Steiner -tree for some ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when has arbitrary size. In addition, we prove that deciding whether is in some Steiner -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.

关键词： complexity of algorithms Enumerative combinatorics Steiner convexity Steiner tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：