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

dynamic algorithms via the primal-dual method

INFORMATION AND COMPUTATION 2018年 261卷 219-239页

作者： Bhattacharya, Sayan Henzinger, Monika Italiano, Giuseppe Univ Warwick Coventry W Midlands England Univ Vienna Vienna Austria Univ Roma Tor Vergata Rome Italy

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O(f(2))-approximately optimal solution in O(f center dot log(m + n)) amortized update time, where fis the maximum "frequency" of an element, nis the number of sets, and mis the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O(1)-approximately optimal solution in O(log3n) amortized update time, where nis the number of nodes in the graph. (C) 2018 Elsevier Inc. All rights reserved.

关键词： dynamic algorithms Primal-dual method Data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for classes of constraint satisfaction problems

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期259卷 287-305页

作者： Frigioni, D Marchetti-Spaccamela, AT Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

Many fundamental tasks in artificial intelligence and in combinatorial optimization can be formulated as a constant Satisfaction Problem (CSP). It is the problem of finding an assignment of values for a set of variables, each defined on a finite domain of feasible values, subject to a given collection of constraints. Each constraint is defined over a set of variables and specifies the allowed combinations of values as a collection of tuples. In general, the problem of finding a solution to a CSP is NP-complete, but in some cases it has shown to be polynomially solvable. We consider the dynamic version of some polynomially solvable constraint satisfaction problems, and present solutions that are better than recomputing everything from scratch after each update. The updates we consider are either restrictions, i.e., deletions of values from existing constraints and introduction of new constraints, or relaxations, i.e., insertions of values or deletions of constraints. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： constraint satisfaction problem network of constraints dynamic algorithms consistency backtrack-free search amortized complexity

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for monotonic interval scheduling problem

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 227-242页

作者： Gavruskin, Alexander Khoussainov, Bakhadyr Kokho, Mikhail Liu, Jiamou Univ Auckland Dept Comp Sci Auckland 1 New Zealand Auckland Univ Technol Sch Comp & Math Sci Auckland New Zealand

We investigate dynamic algorithms for the interval scheduling problem. We focus on the case when the set of intervals is monotonic. This is when no interval properly contains another interval. We provide two data structures for representing the intervals that allow efficient insertion, removal and various query operations. The first dynamic algorithm, based on the data structure called compatibility forest, runs in amortised time O (log(2) n) for insertion and removal and O (logn) for query. The second dynamic algorithm, based on the data structure called linearised tree, runs in time O (logn) for insertion, removal and query. We discuss differences and similarities of these two data structures through theoretical and experimental results. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Interval scheduling dynamic algorithms Data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for graphs of bounded treewidth

引用

ALGORITHMICA 2000年第3-4期27卷 292-315页

作者： Hagerup, T Goethe Univ Frankfurt Fachbereich Informat D-60054 Frankfurt Germany

The formalism of monadic second-order (MS) logic has been very successful in unifying a large number of algorithms for graphs of bounded treewidth. We extend the elegant framework of MS logic from static problems to dynamic problems, in which queries about MS properties of a graph of bounded treewidth are interspersed with updates of vertex and edge labels. This allows us to unify and occasionally strengthen a number of scattered previous results obtained in an ad hoc manner and to enable solutions to a wide range of additional problems to be derives automatically. As an auxiliary result of independent interest, we dynamize a data structure of Chazelle for answering queries about products of labels along paths in a tree with edges labeled by elements of a semigroup.

关键词： dynamic algorithms graph algorithms treewidth monadic second-order logic path queries

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for the Massively Parallel Computation Model 19

Dynamic Algorithms for the Massively Parallel Computation Mo...

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Italiano, Giuseppe F. Lattanzi, Silvio Mirrokni, Vahab S. Parotsidis, Nikos LUISS Univ Rome Italy Google Res New York NY USA Google Res Zurich Switzerland Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450361842

The Massive Parallel Computing (MPC) model gained popularity during the last decade and it is now seen as the standard model for processing large scale data. One significant shortcoming of the model is that it assumes to work on static datasets while, in practice, real world datasets evolve continuously. To overcome this issue, in this paper we initiate the study of dynamic algorithms in the MPC model. We first discuss the main requirements for a dynamic parallel model and we show how to adapt the classic MPC model to capture them. Then we analyze the connection between classic dynamic algorithms and dynamic algorithms in the MPC model. Finally, we provide new efficient dynamic MPC algorithms for a variety of fundamental graph problems, including connectivity, minimum spanning tree and matching.

关键词： massive parallel computing dynamic algorithms mapreduce model

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for Visibility Polygons in Simple Polygons

引用

International Journal of Computational Geometry and Applications 2020年第1期30卷 51-78页

作者： Inkulu, R. Sowmya, K. Thakur, Nitish P. Department of Computer Science and Engineering IIT Guwahati India

We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and deletions to the simple polygon. A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point q due to the insertion (resp. deletion) of vertex v to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of q due to the insertion (resp. deletion) of v. An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point p in 2 amid vertex insertions and deletions to the simple polygon. If p is not exterior to the current simple polygon, then the visibility polygon of p is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of p. An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment pq due to the insertion of vertex v to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at p and q due to the insertion of v. An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple

关键词： Computational geometry dynamic algorithms visibility

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms against an Adaptive Adversary: Generic Constructions and Lower Bounds 2022

Dynamic Algorithms against an Adaptive Adversary: Generic Co...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Beimel, Amos Kaplan, Haim Mansour, Yishay Nissim, Kobbi Saranurak, Thatchaphol Stemmer, Uri Ben Gurion Univ Negev Beer Sheva Israel Tel Aviv Univ Google Res Tel Aviv Israel Georgetown Univ Washington DC USA Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9781450392648

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time;the goal is to design an algorithm in which computing a solution to the updated input is done more efficiently than computing the solution from scratch. A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. Our results are as follows. We give a general reduction transforming a dynamic algorithm against an oblivious adversary to a dynamic algorithm robust against an adaptive adversary. This reduction maintains several copies of the oblivious algorithm and uses differential privacy to protect their random bits. Using this reduction we obtain dynamic algorithms against an adaptive adversary with improved update and query times for global minimum cut, all pairs distances, and all pairs effective resistance. We further improve our update and query times by showing how to maintain a sparsifier over an expander decomposition that can be refreshed fast. This fast refresh enables it to be robust against what we call a blinking adversary that can observe the output of the algorithm only following refreshes. We believe that these techniques will prove useful for additional problems. On the flip side, we specify dynamic problems that, assuming a random oracle, every dynamic algorithm that solves them against an adaptive adversary must be polynomially slower than a rather straightforward dynamic algorithm that solves them against an oblivious adversary. We first show a separation result for a search problem and then show a separation result for an estimati

关键词： dynamic algorithms adaptive adversaries differential privacy

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms and Asymptotic Theory for Lp-Norm Data Analysis

Dynamic Algorithms and Asymptotic Theory for Lp-Norm Data An...

引用

作者： Dhanaraj, Mayur Rochester Institute of Technology

学位级别：Ph.D., Doctor of Philosophy

The focus of this dissertation is the development of outlier-resistant stochastic algorithms for Principal Component Analysis (PCA) and the derivation of novel asymptotic theory for Lp-norm Principal Component Analysis (Lp-PCA). Modern machine learning and signal processing applications employ sensors that collect large volumes of data measurements that are stored in the form of data matrices, that are often massive and need to be efficiently processed in order to enable machine learning algorithms to perform effective underlying pattern discovery. One such commonly used matrix analysis technique is PCA. Over the past century, PCA has been extensively used in areas such as machine learning, deep learning, pattern recognition, and computer vision, just to name a few. PCA's popularity can be attributed to its intuitive formulation on the L2-norm, availability of an elegant solution via the singular-value-decomposition (SVD), and asymptotic convergence guarantees. However, PCA has been shown to be highly sensitive to faulty measurements (outliers) because of its reliance on the outlier-sensitive L2-norm. Arguably, the most straightforward approach to impart robustness against outliers is to replace the outlier-sensitive L2-norm by the outlier-resistant L1-norm, thus formulating what is known as L1-PCA. Exact and approximate solvers are proposed for L1-PCA in the literature. On the other hand, in this big-data era, the data matrix may be very large and/or the data measurements may arrive in streaming fashion. Traditional L1-PCA algorithms are not suitable in this setting. In order to efficiently process streaming data, while being resistant against outliers, we propose a stochastic L1-PCA algorithm that computes the dominant principal component (PC) with formal convergence guarantees. We further generalize our stochastic L1-PCA algorithm to find multiple components by propose a new PCA framework that maximizes the recently proposed Barron loss. Leveraging Barron loss yi

关键词： Asymptotic Lp-PCA dynamic algorithms L1-PCA Lp-PCA PCA Reliable data analysis

来源：评论

学校读者我要写书评

暂无评论

Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence

引用

ALGORITHMICA 2002年第2期33卷 168-182页

作者： Korupolu, MR Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms, which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph, We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for edge connectivity and O(log n) amortized time per operation for cycle equivalence, The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log(3)n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem.

关键词： dynamic algorithms graph algorithms cycle equivalence connected graphs edge and vertex connectivity randomized algorithms compiler optimization

来源：评论

学校读者我要写书评

暂无评论

Arboricity, h-index, and dynamic algorithms

引用

THEORETICAL COMPUTER SCIENCE 2012年 426卷 75-90页

作者： Lin, Min Chih Soulignac, Francisco. J. Szwarcfiter, Jayme L. Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Inst Calculo Buenos Aires DF Argentina Univ Fed Rio de Janeiro Inst Matemat NCE BR-20001970 Rio De Janeiro RJ Brazil COPPE BR-20001970 Rio De Janeiro RJ Brazil

We propose a new data structure for manipulating graphs, called h-graph, which is particularly suited for designing dynamic algorithms. The structure itself is simple, consisting basically of a triple of elements, for each vertex of the graph. The overall size of all triples is O(n + m), for a graph with n vertices and m edges. We describe algorithms for performing the basic operations related to dynamic applications, as insertions and deletions of vertices or edges, and adjacency queries. The data structure employs a technique first described by Chiba and Nishizeki [Chiba, Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1) (1985) 210-223], and relies on the arboricity of graphs. Using the proposed data structure, we describe several dynamic algorithms for solving problems as listing the cliques of a given size, recognizing diamond-free graphs, and finding simple, simplicial and dominated vertices. These algorithms are the first of their kind to be proposed in the literature. In fact, the dynamic algorithms for the above problems lead directly to new static algorithms, and using the data structure we also design new static algorithms for the problems of counting subgraphs of size 4, recognizing cop-win graphs and recognizing strongly chordal graphs. The complexities of all of the proposed static algorithms improve over the complexities of the so far existing algorithms, for graphs of low arboricity. In addition, for the problems of counting subgraphs of size 4 and recognizing diamond-free graphs, the improvement is general. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Arboricity Cop-win graphs Data structures Diamond-free graphs dynamic algorithms h-index Strongly chordal graphs

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：