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

algorithms FOR WEIGHTED MATCHING GENERALIZATIONS I: BIPARTITE GRAPHS, b-MATCHING, AND UNWEIGHTED f-FACTORS

SIAM JOURNAL ON COMPUTING 2021年第2期50卷 440-486页

作者： Gabow, Harold N. Sankowski, Piotr Univ Colorado Dept Comp Sci Boulder CO 80309 USA Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland

Let G = (V;E) be a weighted graph or multigraph, with f or b a function assigning a nonnegative integer to each vertex. An f-factor is a subgraph whose degree function is f;a perfect b-matching is a b-factor in the graph formed from G by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum f-factor, i.e., f -factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum f -factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum b-matching, i.e., maximum weight b-matching. It is almost identical to its special case b 1, ordinary weighted matching. The time is O (Wb(V)!) for W the maximum magnitude of an edge weight, b(V) = P v2V b(v), and ! < 2:373 the exponent of matrix multiplication. An algebraic algorithm to find an f-factor. The time is O(f (V)!) for f (V) = P v2V f (v). The specialization of the f -factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite f factors. This improves the known complexity bounds for vertex capacitated max-flow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas.

关键词： algebraic algorithms matchings factors shortest paths

来源：评论

学校读者我要写书评

暂无评论

The Persistent Homology of a Self-Map

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2015年第5期15卷 1213-1244页

作者： Edelsbrunner, Herbert Jablonski, Grzegorz Mrozek, Marian IST Austria Inst Sci & Technol Austria Klosterneuburg Austria Jagiellonian Univ Fac Math & Comp Sci Div Computat Math Krakow Poland

Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.

关键词： Discrete dynamical systems Computational topology Persistent homology Category theory algebraic algorithms Convergence Stability Computational experiments

来源：评论

学校读者我要写书评

暂无评论

Decoding Reed-Muller Codes over Product Sets

引用

THEORY OF COMPUTING 2017年 13卷 1-38页

作者： Kim, John Y. Kopparty, Swastik Virtu Financial Austin TX 78746 USA Rutgers State Univ Dept Math New Brunswick NJ USA Rutgers State Univ Dept Comp Sci New Brunswick NJ USA

We give a polynomial-time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set S-m, for every d < vertical bar S vertical bar. Previously known algorithms could achieve this only if the set S had some very special algebraic structure, or if the degree d was significantly smaller than vertical bar S vertical bar. We also give a near-linear-time randomized algorithm, based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1- epsilon) vertical bar S vertical bar for constant epsilon > 0. Our result gives an m-dimensional generalization of the well-known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.

关键词： error-correcting codes Reed-Muller codes algebraic algorithms Schwartz-Zippel lemma

来源：评论

学校读者我要写书评

暂无评论

An application of the modified Leverrier-Faddeev algorithm to the spectral decomposition of symmetric block-circulant matrices

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2006年第1期50卷 89-106页

作者： Gower, JC Open Univ Dept Stat Milton Keynes MK7 6AA Bucks England

The Leverrier-Faddeev algorithm is little-known but, in a modified form, is useful for deriving the algebraic, rather than numerical, spectral structure of matrices occurring in statistical methodology. An example is given of deriving the spectral decomposition of any symmetric block-circulant matrix, which in turn provides the singular value decomposition of any block-circulant matrix. Such problems arise as short-cuts to certain computations that arise in special forms of principal components analysis and correspondence analysis. (c) 2004 Elsevier B.V. All rights reserved.

关键词： algebraic algorithms Leverrier Faddeev block-circulants spectral decomposition singular value decomposition

来源：评论

学校读者我要写书评

暂无评论

Grobner bases and systems theory

引用

MULTIDIMENSIONAL SYSTEMS AND SIGNAL PROCESSING 2001年第3-4期12卷 223-251页

作者： Buchberger, B Johannes Kepler Univ Linz Symbol Computat Res Inst A-4040 Linz Austria

We present the basic concepts and results of Grobner bases theory for readers working or interested in systems theory. The concepts and methods of Grobner bases theory are presented by examples. No prerequisites, except some notions of elementary mathematics, are necessary for reading this paper. The two main properties of Grobner bases, the elimination property and the linear independence property, are explained. Most of the many applications of Grobner bases theory, in particular applications in systems theory, hinge on these two properties. Also, an algorithm based on Grobner bases for computing complete systems of solutions ("syzygies") for linear diophantine equations with multivariate polynomial coefficients is described. Many fundamental problems of systems theory can be reduced to the problem of syzygies computation.

关键词： Grobner bases algorithmic systems theory computer algebra algebraic algorithms polynomial ideals elimination residue class rings syzygies polynomial diophantine equations

来源：评论

学校读者我要写书评

暂无评论

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

引用

ALGORITHMICA 2016年第2期76卷 536-568页

作者： Miyazawa, Flavio K. Pedrosa, Lehilton L. C. Schouery, Rafael C. S. Sviridenko, Maxim Wakabayashi, Yoshiko Univ Estadual Campinas Inst Comp Campinas SP Brazil Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil Yahoo Labs New York NY USA

We consider the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height , for some arbitrarily small number . For this problem, we obtain an asymptotic approximation scheme (APTAS) that is polynomial on , and thus may be given as part of the problem input. For the special case that is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height using no more than the number of bins in an optimal packing without resource augmentation. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. Our algorithms are the first approximation schemes for circle packing problems, and are based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the L-p-norm.

关键词： Circle bin packing Circle strip packing Asymptotic approximation scheme Resource augmentation scheme Sphere packing algebraic algorithms

来源：评论

学校读者我要写书评

暂无评论

Computational ideal theory in finitely generated extension rings

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期244卷 1-33页

作者： Apel, J Univ Leipzig Fak Math & Informat D-04109 Leipzig Germany

Since Buchberger introduced the theory of Grobner bases in 1965 it has become an important tool in constructive algebra and, nowadays, Buchberger's method is fundamental for many algorithms in the theory of polynomial ideals and algebraic geometry. Motivated by the results in polynomial rings a lot of possibilities to generalize the ideas to other types of rings have been investigated. The perhaps most general concept, though it does not cover all possible extensions, is the theory of graded structures due to Robbiano and Mom. But in order to obtain algorithmic solutions for the computation of Grobner bases it needs additional computability assumptions. In this paper we introduce natural graded structures of finitely generated extension rings and present subclasses of such structures which allow uniform algorithmic solutions of the basic problems in the associated graded ring and, hence, of the computation of Grobner bases with respect to the graded structure. Among the considered rings there are many of the known generalizations. But, in addition, a wide class of rings appears first time in the context of algorithmic Grobner basis computations. Finally, we discuss which conditions could be changed in order to find further effective Grobner structures and it will turn out that the most interesting constructive instances of graded structures are covered by our results. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： computable algebraic structures algebraic algorithms Groebner bases in graded structures

来源：评论

学校读者我要写书评

暂无评论

Finding Path Motifs in Large Temporal Graphs Using algebraic Fingerprints

引用

BIG DATA 2020年第5期8卷 335-362页

作者： Thejaswi, Suhas Gionis, Aristides Lauri, Juho Aalto Univ Dept Comp Sci Aalto 00076 Finland KTH Royal Inst Technol Dept Comp Sci Stockholm Sweden

We study a family of pattern-detection problems in vertex-colored temporal graphs. In particular, given a vertex-colored temporal graph and a multiset of colors as a query, we search for temporal paths in the graph that contain the colors specified in the query. These types of problems have several applications, for example, in recommending tours for tourists or detecting abnormal behavior in a network of financial transactions. For the family of pattern-detection problems we consider, we establish complexity results and design an algebraic-algorithmic framework based on constrained multilinear sieving. We demonstrate that our solution scales to massive graphs with up to a billion edges for a multiset query with 5 colors and up to 100 million edges for a multiset query with 10 colors, despite the problems being non-deterministic polynomial time-hard. Our implementation, which is publicly available, exhibits practical edge-linear scalability and is highly optimized. For instance, in a real-world graph dataset with >6 million edges and a multiset query with 10 colors, we can extract an optimal solution in <8 minutes on a Haswell desktop with four cores.

关键词： algebraic algorithms constrained multilinear sieving pattern detection temporal paths temporal patterns

来源：评论

学校读者我要写书评

暂无评论

Determining cyclicity of finite modules

引用

JOURNAL OF SYMBOLIC COMPUTATION 2016年 73卷 153-156页

作者： Lenstra, H. W., Jr. Silverberg, A. Leiden Univ Math Inst NL-2300 RA Leiden Netherlands Univ Calif Irvine Dept Math Irvine CA 92697 USA

We present a deterministic polynomial-time algorithm that determines whether a finite module over a finite commutative ring is cyclic, and if it is, outputs a generator. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： algebraic algorithms Finite rings Cyclic modules

来源：评论

学校读者我要写书评

暂无评论

SPEEDING UP AN OVERRELAXATION METHOD OF DIVISION IN RADIX-2N MACHINE

引用

COMMUNICATIONS OF THE ACM 1983年第3期26卷 216-220页

作者： ASAI, H CHENG, CK Christopher Newport College Newport News VA

For normalized floating point division, digital computers can take advantage of a division process that uses an iterative multiplying operation instead of repeated subtractions. An improvement of this division process by using accelerating constants in the overrelaxation has previously been proposed. Multiplication by a chosen accelerating constant accelerates the process of generating accurate digits of a quotient in division. We propose a further improvement by generalizing the accelerating constants in the overrelaxation method. Two benefits resulting from this improvement promise to yield faster division in digital computers.

关键词： Wilkes-Harvard scheme algebraic algorithms convergence convergence division iterative multiplication overrelaxation power series truncation error

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：