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

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Assadi, Sepehr Behnezhad, Soheil Khanna, Sanjeev Li, Huan Rutgers State Univ New Brunswick NJ 08903 USA Northeastern Univ Boston MA USA Univ Penn Philadelphia PA USA

ISBN: (纸本)9781450399135

We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs: (i) A deterministic single-pass streaming algorithm that finds a (1 - o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. (ii) A randomized fully dynamic algorithm that with high probability maintains a (1 - o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log* n)T(1) factor. Nevertheless, in each case, they show that the "right" answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemeredi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

关键词： Maximum Matching Streaming algorithms dynamic algorithms Regularity Lemma

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal dynamic Rounding of Fractional Matchings in Bipartite Graphs 2024

Near-Optimal Dynamic Rounding of Fractional Matchings in Bip...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Bhattacharya, Sayan Kiss, Peter Sidford, Aaron Wajc, David Univ Warwick Coventry W Midlands England Stanford Univ Stanford CA 94305 USA Technion Israel Inst Technol Haifa Israel

ISBN: (纸本)9798400703836

We study dynamic (1 - epsilon)-approximate rounding of fractional matchings-a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contribution is a surprisingly simple deterministic rounding algorithm in bipartite graphs with amortized update time O(epsilon(-1) log(2) (epsilon(-1) center dot n)), matching an (unconditional) recourse lower bound of Omega(epsilon(-1)) up to logarithmic factors. Moreover, this algorithm's update time improves provided the minimum (non-zero) weight in the fractional matching is lower bounded throughout. Combining this algorithm with novel dynamic partial rounding algorithms to increase this minimum weight, we obtain a number of algorithms that improve this dependence on n. For example, we give a high-probability randomized algorithm with (O) over tilde (epsilon(-1) center dot ( log log n)(2))-update time against adaptive adversaries. Using our rounding algorithms, we also round known (1 - epsilon)-decremental fractional bipartite matching algorithms with no asymptotic overhead, thus improving on state-of-the-art algorithms for the decremental bipartite matching problem. Further, we provide extensions of our results to general graphs and to maintaining almost-maximal matchings.

关键词： dynamic Matching dynamic algorithms Data Structures

来源：评论

学校读者我要写书评

暂无评论

A dynamic scheduling algorithm with minimum context switches for spacecraft avionics systems

A dynamic scheduling algorithm with minimum context switches...

引用

IEEE Aerospace Conference

作者： Zolfaghari, B Iran Univ Sci & Technol Dept Comp Engn Tehran Iran

ISBN: (纸本)0780381556

Most of the process-scheduling algorithms, which can be exploited by spacecraft avionics systems, fall into one of the two main categories: static algorithms and dynamic algorithms. 12 Static algorithms assign priorities to processes before runtime. These algorithms bound the CPU utilization and require considerable information about the runtime parameters of processes in advance. These disadvantages encourage the spacecraft avionics system designers to exploit dynamic algorithms instead. But these algorithms have their own disadvantages. For example, these algorithms require so many context switches to schedule the processes. This causes a notable overhead in the runtime. One of the well-known dynamic algorithms is the MLF (Minimum Laxity First) algorithm. The MLF algorithm suffers from a serious problem (in addition to the need for so many context switches). This paper proposes a novel dynamic algorithm called Optimized MLF which is an attempt to solve the problems of the MLF algorithm in order to make it more applicable to spacecraft avionics systems. The performance of the proposed scheduling algorithm is evaluated through the use of mathematical modeling as well as simulation results. Both the mathematical model and simulation results show that the optimized MLF algorithm requires less context switches than the traditional MLF and makes the MLF algorithm more applicable to spacecraft avionics systems.

关键词： avionics space vehicle electronics dynamic scheduling optimisation mathematical analysis dynamic scheduling algorithm minimum context switches spacecraft avionics systems process scheduling algorithms CPU utilization minimum laxity first algorithm mathematical modeling avionics dynamic scheduling space vehicle electronics mathematical modeling mathematical analysis Scheduling algorithms dynamic algorithms Spacecraft Switches algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully-dynamic Submodular Cover with Bounded Recourse 61

Fully-Dynamic Submodular Cover with Bounded Recourse

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Gupta, Anupam Levin, Roie Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9781728196213

In submodular covering problems, we are given a monotone, nonnegative submodular function f : 2(N) -> R+ and wish to find the min-cost set S subset of N such that f(S) = f(N). When f is a coverage function, this captures SETCOVER as a special case. We introduce a general framework for solving such problems in a fully-dynamic setting where the function f changes over time, and only a bounded number of updates to the solution (a.k.a. recourse) is allowed. For concreteness, suppose a nonnegative monotone submodular integer-valued function g(t) is added or removed from an active set G((t)) at each time t. If f((t)) = Sigma(g is an element of G(t)) g is the sum of all active functions, we wish to maintain a competitive solution to SUBMODULARCOVER for f((t)) as this active set changes, and with low recourse. For example, if each g(t) is the (weighted) rank function of a matroid, we would be dynamically maintaining a low-cost common spanning set for a changing collection of matroids. We give an algorithm that maintains an O(log(f(max)/f(min)))-competitive solution, where f(max), f(min) are the largest/smallest marginals of f((t)). The algorithm guarantees a total recourse of O(log(c(max)/c(min)).Sigma(t <= T) g(t)(N)), where C-max,C-min are the largest/smallest costs of elements in N. This competitive ratio is best possible even in the offline setting, and the recourse bound is optimal up to the logarithmic factor. For monotone submodular functions that also have positive mixed third derivatives, we show an optimal recourse bound of O(Sigma(t <= T) g(t)(N)). This structured class includes set-coverage functions, so our algorithm matches the known O(log n)-competitiveness and O(1) recourse guarantees for fully-dynamic SETCOVER. Our work simultaneously simplifies and unifies previous results, as well as generalizes to a significantly larger class of covering problems. Our key technique is a new potential function inspired by Tsallis entropy. We also extensively use the idea

关键词： submodular optimization online algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time 64

Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear ...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Bhattacharya, Sayan Kiss, Peter Saranurak, Thatchaphol Univ Warwick Coventry W Midlands England Univ Michighan Ann Arbor MI USA

ISBN: (纸本)9798350318944

We show a fully dynamic algorithm for maintaining (1 + epsilon)-approximate size of maximum matching of the graph with n vertices and m edges using m(0.5-Omega epsilon(1)) update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16], [Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for (1, epsilon n)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.

关键词： Approximate Maximum Matching dynamic algorithms Sublinear Algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Abboud, Amir Williams, Virginia Vassilevska Stanford Univ Dept Comp Sci Palo Alto CA 94304 USA

ISBN: (纸本)9781479965175

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1) Is the 3SUM problem on n numbers in O(n(2-epsilon)) time for some epsilon > 0? 2) Can one determine the satisfiability of a CNF formula on n variables and poly n clauses in O((2 - epsilon)(n) poly n) time for some epsilon > 0? 3) Is the All Pairs Shortest Paths problem for graphs on n vertices in O(n(3-epsilon)) time for some epsilon > 0? 4) Is there a linear time algorithm that detects whether a given graph contains a triangle? 5) Is there an O(n(3-epsilon)) time combinatorial algorithm for nxn Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu[STOC 2010].

关键词： dynamic algorithms all pairs shortest paths 3SUM lower bounds

来源：评论

学校读者我要写书评

暂无评论

Vertex Guarding for dynamic Orthogonal Art Galleries

引用

International Journal of Computational Geometry and Applications 2021年第2期31卷 123-140页

作者： Banerjee, Debangshu Inkulu, R. Department of Computer Science and Engineering Iit Guwahati India

We devise an algorithm for surveying a dynamic orthogonal polygonal domain by placing one guard at each vertex in a subset of its vertices, i.e., whenever an orthogonal polygonal domain ′ is modified to result in another orthogonal polygonal domain, our algorithm updates the set of vertex guards surveying ′ so that the updated guard set surveys. Our algorithm modifies the guard placement in O(klg (n + n′)) amortized time, while ensuring the updated orthogonal polygonal domain with h holes and n vertices is guarded using at most (n + 2h)/4 vertex guards. For the special case of the initial orthogonal polygon being hole-free and each update resulting in a hole-free orthogonal polygon, our guard update algorithm takes O(klg (n + n′)) worst-case time. Here, n′ and n are the number of vertices of the orthogonal polygon before and after the update, respectively;and, k is the sum of |n-n′| and the number of updates to a few structures maintained by our algorithm. Further, by giving a construction, we show it suffices for the algorithm to consider only the case in which the parity of the number of reflex vertices of both ′ and are equal. © 2021 World Scientific Publishing Company.

关键词： Art gallery Computational geometry dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance in the Fully dynamic Model 64

Approximating Edit Distance in the Fully Dynamic Model

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Kociumaka, Tomasz Mukherjee, Anish Saha, Barna Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Univ Warwick Coventry W Midlands England Univ Calif Dept Comp Sci & Engn San Diego CA USA

ISBN: (纸本)9798350318944

The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. Given two strings of length at most n, a simple dynamic programming computes their edit distance exactly in O(n(2)) time, which is also the best possible (up to subpolynomial factors) assuming the Strong Exponential Time Hypothesis (SETH). The last few decades have seen tremendous progress in edit distance approximation, where the runtime has been brought down to subquadratic, to near-linear, and even to sublinear at the cost of approximation. In this paper, we study the dynamic edit distance problem where the strings change dynamically as the characters are substituted, inserted, or deleted over time. Each change may happen at any location of either of the two strings. The goal is to maintain the (exact or approximate) edit distance of such dynamic strings while minimizing the update time. The exact edit distance can be maintained in O(n log(2) n) time per update (Charalampopoulos, Kociumaka, Mozes;2020), which is again tight assuming SETH. Unfortunately, even with the unprecedented progress in edit distance approximation in the static setting, strikingly little is known regarding dynamic edit distance approximation. Utilizing the best near-linear-time (Andoni, Nosatzki;2020) and sublinear-time (Goldenberg, Kociumaka, Krauthgamer, Saha;2022) approximation algorithm, an old exact algorithm (Landau and Vishkin;1988), and a generic dynamic strings implementation (Mehlhorn, Sundar, Uhrig;1996), it is possible to achieve an O(n(c))-approximation in n(0.5-c+o(1)) update time for any constant c is an element of [0, 1/6]. Improving upon this trade-off, characterized by the approximation-ratio and update-time product n(0.5+o(1)), remains wide open. The contribution of this work is a dynamic n(o(1))-approximation algorithm with amortized expected update time of n(o(1)). In other w

关键词： edit distance dynamic algorithms approximation

来源：评论

学校读者我要写书评

暂无评论

Parallel Batch-dynamic Minimum Spanning Forest and the Efficiency of dynamic Agglomerative Graph Clustering 22

Parallel Batch-Dynamic Minimum Spanning Forest and the Effic...

引用

34th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Tseng, Tom Dhulipala, Laxman Shun, Julian MIT CSAIL Cambridge MA 02139 USA Univ Maryland College Pk MD USA

ISBN: (纸本)9781450391467

Hierarchical agglomerative clustering (HAC) is a popular algorithm for clustering data, but despite its importance, no dynamic algorithms for HAC with good theoretical guarantees exist. In this paper, we study dynamic HAC on edge-weighted graphs. As single-linkage HAC reduces to computing a minimum spanning forest (MSF), our first result is a parallel batch-dynamic algorithm for maintaining MSFs. On a batch of k edge insertions or deletions, our batch-dynamic MSF algorithm runs in O(k log(6) n) expected amortized work and O(log(4) n) span with high probability. It is the first fully dynamic MSF algorithm handling batches of edge updates with polylogarithmic work per update and polylogarithmic span. Using our MSF algorithm, we obtain a parallel batch-dynamic algorithm that can answer queries about single-linkage graph HAC clusters. Our second result is that dynamic graph HAC is significantly harder for other common linkage functions. For example, assuming the strong exponential time hypothesis, dynamic graph HAC requires Omega(n(1-o(1))) work per update or query on a graph with n vertices for complete linkage, weighted average linkage, and average linkage. For complete linkage and weighted average linkage, the bound still holds even for incremental or decremental algorithms and even if we allow poly(n)-approximation. For average linkage, the bound weakens to Omega(n(1/2-o(1))) for incremental and decremental algorithms, and the bounds still hold when allowing n(o(1))-approximation.

关键词： Parallel algorithms dynamic algorithms Graph Clustering

来源：评论

学校读者我要写书评

暂无评论

Repetition Detection in a dynamic String 27

Repetition Detection in a Dynamic String

引用

27th Annual European Symposium on algorithms (ESA)

作者： Amir, Amihood Boneh, Itai Charalampopoulos, Panagiotis Kondratovsky, Eitan Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England Interdisciplinary Ctr Herzliya Efi Arazi Sch Comp Sci Herzliyya Israel

ISBN: (纸本)9783959771245

A string UU for a non-empty string U is called a square. Squares have been well-studied both from a combinatorial and an algorithmic perspective. In this paper, we are the first to consider the problem of maintaining a representation of the squares in a dynamic string S of length at most n. We present an algorithm that updates this representation in n(o)(1) time. This representation allows us to report a longest square-substring of S in O(1) time and all square-substrings of S in O(output) time. We achieve this by introducing a novel tool - maintaining prefix-suffix matches of two dynamic strings. We extend the above result to address the problem of maintaining a representation of all runs (maximal repetitions) of the string. Runs are known to capture the periodic structure of a string, and, as an application, we show that our representation of runs allows us to efficiently answer periodicity queries for substrings of a dynamic string. These queries have proven useful in static pattern matching problems and our techniques have the potential of offering solutions to these problems in a dynamic text setting.

关键词： string algorithms dynamic algorithms squares repetitions runs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：