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

Fully dynamic algorithms for Euclidean Steiner Tree 1

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Chan, T-H Hubert Goranci, Gramoz Jiang, Shaofeng H-C Wang, Bo Xue, Quan Univ Hong Kong Hong Kong Peoples R China Univ Vienna Vienna Austria Peking Univ Beijing Peoples R China

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of terminal points X in R-d, possibly using points not in X which are called Steiner points. Even though near-linear time (1+ epsilon)-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a (1+epsilon)-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time O(poly log n) with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP sub-problems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries.

关键词： Steiner Tree dynamic algorithms Approximation Schemes

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic algorithms for Longest Increasing Subsequence 2021

Improved Dynamic Algorithms for Longest Increasing Subsequen...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Kociumaka, Tomasz Seddighin, Saeed Univ Calif Berkeley Berkeley CA 94720 USA Toyota Technol Inst Chicago Chicago IL USA

ISBN: (纸本)9781450380539

We study dynamic algorithms for the longest increasing subsequence (LIS) problem. A dynamic LIS algorithm maintains a sequence subject to operations of the following form arriving one by one: insert an element, delete an element, or substitute an element for another. After each update, the algorithm must report the length of the longest increasing subsequence of the current sequence. Our main contribution is the first exact dynamic LIS algorithm with sublinear update time. More precisely, we present a randomized algorithm that performs each operation in time (O) over tilde (n(4/5)) and, after each update, reports the answer to the LIS problem correctly with high probability. We use several novel techniques and observations for this algorithm that may find applications in future work. In the second part of the paper, we study approximate dynamic LIS algorithms, which are allowed to underestimate the solution size within a bounded multiplicative factor. In this setting, we give a deterministic (1 - o(1))-approximation algorithm with update time O(n(o(1))). This result improves upon the previous work of Mitzenmacher and Seddighin (STOC'20) that provides an Omega(epsilon(O(1/epsilon)))-approximation algorithm with update time (O) over tilde (n(epsilon)) for any epsilon > 0.

关键词： Longest Increasing Subsequence dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Recent Advances in Fully dynamic Graph algorithms - A Quick Reference Guide

引用

ACM Journal of Experimental Algorithmics 2022年第11期27卷 1-45页

作者： Hanauer, Kathrin Henzinger, Monika Schulz, Christian Faculty of Computer Science University of Vienna Währinger Str. 29 Vienna Vienna1090 Austria Heidelberg University Im Neuenheimer Feld 205 Baden-Württemberg Heidelberg69120 Germany

In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms. © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： dynamic algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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 via the primal-dual method

引用

INFORMATION AND COMPUTATION 2018年第Part2期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

来源：评论

学校读者我要写书评

暂无评论

ON dynamic algorithms FOR FACTORIZATION INVARIANTS IN NUMERICAL MONOIDS

引用

MATHEMATICS OF COMPUTATION 2017年第307期86卷 2429-2447页

作者： Barron, Thomas O'Neill, Christopher Pelayo, Roberto Univ Kentucky Dept Math Lexington KY 40506 USA Texas A&M Univ Dept Math College Stn TX 77843 USA Univ Calif Davis Dept Math One Shields Ave Davis CA 95616 USA Univ Hawaii Dept Math Hilo HI 96720 USA

Studying the factorization theory of numerical monoids relies on understanding several important factorization invariants, including length sets, delta sets, and w-primality. While progress in this field has been accelerated by the use of computer algebra systems, many existing algorithms are computationally infeasible for numerical monoids with several irreducible elements. In this paper, we present dynamic algorithms for the factorization set, length set, delta set, and w-primality in numerical monoids and demonstrate that these algorithms give significant improvements in runtime and memory usage. In describing our dynamic approach to computing w-primality, we extend the usual definition of this invariant to the quotient group of the monoid and show that several useful results naturally extend to this broader setting.

关键词： Monoid computer use factorization dynamic algorithms Quotient group dynamic algorithms Runtime Invariant

来源：评论

学校读者我要写书评

暂无评论

Online and dynamic algorithms for Set Cover 2017

Online and Dynamic Algorithms for Set Cover

引用

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

作者： Gupta, Anupam Krishnaswamy, Ravishankar Kumar, Amit Panigrahi, Debmalya Carnegie Mellon Univ Pittsburgh PA 15213 USA Microsoft Res Bengaluru India IIT Delhi New Delhi India Duke Univ Durham NC 27706 USA

ISBN: (纸本)9781450345286

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offine algorithms for set cover. The former leads to a competitive ratio of O(log n(t)), where n(t) is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on f(t), the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

关键词： Set cover recourse dynamic algorithms competitive ratio online algorithms vertex cover graph matching hypergraph matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：