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

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

作者： van den Brand, Jan Nanongkai, Danupon Saranurak, Thatchaphol KTH Royal Inst Technol Stockholm Sweden Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9781728149523

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems whose complexity is not yet well understood, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachability, distances, maximum matching size, and k-paths/cycles in a graph. Understanding the complexity of dynamic matrix inverse is a key to understand these problems. In this paper, we present (i) improved algorithms for dynamic matrix inverse and their extensions to some incremental/look-ahead variants, and (ii) variants of the Online Matrix-Vector conjecture [Henzinger et al. STOC'15] that, if true, imply that these algorithms are tight. Our algorithms automatically lead to faster dynamic algorithms for the aforementioned problems, some of which are also tight under our conjectures, e.g. reachability and maximum matching size (closing the gaps for these two problems was in fact asked by Abboud and V. Williams [FOCS'14]). Prior best bounds for most of these problems date back to more than a decade ago [Sankowski FOCS'04, COCOON'05, SODA'07;Kavitha FSTTCS'08;Mucha and Sankowski Algorithmica'10;Bosek et al. FOCS'14]. Our improvements stem mostly from the ability to use fast matrix multiplication "one more time", to maintain a certain transformation matrix which could be maintained only combinatorially previously (i.e. without fast matrix multiplication). Oddly, unlike other dynamic problems where this approach, once successful, could be repeated several times ("bootstrapping"), our conjectures imply that this is not the case for dynamic matrix inverse and some related problems. However, when a small additional "look-ahead" information is provided we can perform such repetition to drive the bounds down further.

关键词： data structures dynamic algorithms dynamic matrix inverse determinant adjoint reachability matching

来源：评论

学校读者我要写书评

暂无评论

Deterministic dynamic Matching in O(1) Update Time

引用

ALGORITHMICA 2020年第4期82卷 1057-1080页

作者： Bhattacharya, Sayan Chakrabarty, Deeparnab Henzinger, Monika Univ Warwick Coventry England Dartmouth Coll Dept Comp Sci 6211 Sudikoff Lab Hanover NH 03755 USA Univ Vienna Vienna Austria

We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011), Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015);it had an approximation ratio of (2 + epsilon) and an amortized update time of O(log n/epsilon(2)). Our result can be generalized to give a fully dynamic O( f(3))-approximate algorithm with O( f(2)) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.

关键词： dynamic algorithms Data structures Graph algorithms Matching Vertex cover

来源：评论

学校读者我要写书评

暂无评论

A note on improved results for one round distributed clique listing

引用

INFORMATION PROCESSING LETTERS 2023年 181卷

作者： Liu, Quanquan C. Northwestern Univ Comp Sci 2233 Tech DrThird Floor Evanston IL 60208 USA

In this note, we investigate listing cliques of arbitrary sizes in bandwidth-limited, dynamic networks. The problem of detecting and listing triangles and cliques was originally studied in great detail by Bonne and Censor-Hillel (ICALP 2019). We extend this study to dynamic graphs where more than one update may occur as well as resolve an open question posed by Bonne and Censor-Hillel (2019). Our algorithms and results are based on some simple observations about listing triangles under various settings and we show that we can list larger cliques using such facts. Specifically, we show that our techniques can be used to solve an open problem posed in the original paper: we show that detecting and listing cliques (of any size) can be done using O (1)-bandwidth after one round of communication under node insertions and node/edge deletions. We conclude with an extension of our techniques to obtain a small bandwidth 1-round algorithm for listing cliques when more than one node insertion/deletion and/or edge deletion update occurs at any time. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Triangle counting Clique counting Distributed algorithms Graph algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic and Internal Longest Common Substring

引用

ALGORITHMICA 2020年第12期82卷 3707-3743页

作者： Amir, Amihood Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands Univ Warsaw Inst Informat Warsaw Poland Samsung R&D Inst Poland Warsaw Poland

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n)-time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to the fully dynamic LCS problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in (O) over tilde (n(2/3)) time, after (O) over tilde (n)-time and space preprocessing. This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, the authors presented an (O) over tilde (n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in (O) over tilde (1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings;specifically, computing the longest palindrome and the Lyndon factorization of a string after a single edit operation. We develop dynamic sublinear-time algorithms for both of these problems as well. We also consider internal LCS queries, that is, queries in which we are to return an LCS of a pair of substrings of S and T. We show that answering such queries is hard in general and propose efficient data structures for several restricted cases.

关键词： Longest common substring String algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Discrete versus Continuous algorithms in dynamics of Affective Decision Making

引用

algorithms 2023年第9期16卷 416-416页

作者： Yukalov, Vyacheslav I. Yukalova, Elizaveta P. Joint Inst Nucl Res Bogolubov Lab Theoret Phys Dubna 141980 Russia Univ Sao Paulo Inst Fis Sao Carlos CP 369 BR-13560970 Sao Carlos Brazil Joint Inst Nucl Res Lab Informat Technol Dubna 141980 Russia

The dynamics of affective decision making is considered for an intelligent network composed of agents with different types of memory: long-term and short-term memory. The consideration is based on probabilistic affective decision theory, which takes into account the rational utility of alternatives as well as the emotional alternative attractiveness. The objective of this paper is the comparison of two multistep operational algorithms of the intelligent network: one based on discrete dynamics and the other on continuous dynamics. By means of numerical analysis, it is shown that, depending on the network parameters, the characteristic probabilities for continuous and discrete operations can exhibit either close or drastically different behavior. Thus, depending on which algorithm is employed, either discrete or continuous, theoretical predictions can be rather different, which does not allow for a uniquely defined description of practical problems. This finding is important for understanding which of the algorithms is more appropriate for the correct analysis of decision-making tasks. A discussion is given, revealing that the discrete operation seems to be more realistic for describing intelligent networks as well as affective artificial intelligence.

关键词： dynamic algorithms affective decision making dynamic decision making affective artificial intelligence probabilistic networks intelligent networks

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Unifying Framework to Identify Dense Subgraphs on Streams: Graph Nuclei to Hypergraph Cores 21

A Unifying Framework to Identify Dense Subgraphs on Streams:...

引用

14th ACM International Conference on Web Search and Data Mining (WSDM)

作者： Gabert, Kasimir Pinar, Ali Catalyurek, Umit, V Georgia Inst Technol Atlanta GA 30332 USA Sandia Natl Labs Livermore CA USA

ISBN: (纸本)9781450382977

Finding dense regions of graphs is fundamental in graph mining. We focus on the computation of dense hierarchies and regions with graph nuclei-a generalization of k-cores and trusses. Static computation of nuclei, namely through variants of 'peeling', are easy to understand and implement. However, many practically important graphs undergo continuous change. dynamic algorithms, maintaining nucleus computations on dynamic graph streams, are nuanced and require significant effort to port between nuclei, e.g., from k-cores to trusses. We propose a unifying framework to maintain nuclei in dynamic graph streams. First, we show no dynamic algorithm can asymptotically beat re-computation, highlighting the need to experimentally understand variability. Next, we prove equivalence between k-cores on a special hypergraph and nuclei. Our algorithm splits the problem into maintaining the special hypergraph and maintaining k-cores on it. We implement our algorithm and experimentally demonstrate improvements up to 10(8) x over re-computation. We show algorithmic improvements on k-cores apply to trusses and outperform truss-specific implementations.

关键词： nucleus decomposition dynamic algorithms k-core k-truss

来源：评论

学校读者我要写书评

暂无评论

Rounding dynamic Matchings against an Adaptive Adversary 2020

Rounding Dynamic Matchings against an Adaptive Adversary

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Wajc, David Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450369794

We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against adaptive adversaries. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries. In contrast, all previous randomized algorithms for this problem assumed a weaker, oblivious, adversary. Our dynamic algorithms against adaptive adversaries include, for any constant epsilon > 0, a (2 + epsilon)-approximate algorithm with constant update time or polylog worst-case update time, as well as (2 - delta)-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time. All these results achieve polynomially better update time to approximation trade-offs than previously known to be achievable against adaptive adversaries.

关键词： dynamic algorithms dynamic Matching Matching Sparsifier Adaptive Adversary

来源：评论

学校读者我要写书评

暂无评论

Just-In-Time Constraint-Based Inference for Qualitative Spatial and Temporal Reasoning

引用

KUNSTLICHE INTELLIGENZ 2020年第2期34卷 259-270页

作者： Sioutis, Michael Univ Bamberg Fac Informat Syst & Appl Comp Sci Weberei 5 D-96047 Bamberg Germany

We discuss a research roadmap for going beyond the state of the art in qualitative spatial and temporal reasoning (QSTR). Simply put, QSTR is a major field of study in Artificial Intelligence that abstracts from numerical quantities of space and time by using qualitative descriptions instead (e.g., precedes, contains, is left of);thus, it provides a concise framework that allows for rather inexpensive reasoning about entities located in space or time. Applications of QSTR can be found in a plethora of areas and domains such as smart environments, intelligent vehicles, and unmanned aircraft systems. Our discussion involves researching novel local consistencies in the aforementioned discipline, defining dynamic algorithms pertaining to these consistencies that can allow for efficient reasoning over changing spatio-temporal information, and leveraging the structures of the locally consistent related problems with regard to novel decomposability and theoretical tractability properties. Ultimately, we argue for pushing the envelope in QSTR via defining tools for tackling dynamic variants of the fundamental reasoning problems in this discipline, i.e., problems stated in terms of changing input data. Indeed, time is a continuous flow and spatial objects can change (e.g., in shape, size, or structure) as time passes;therefore, it is pertinent to be able to efficiently reason about dynamic spatio-temporal data. Finally, these tools are to be integrated into the larger context of highly active areas such as neuro-symbolic learning and reasoning, planning, data mining, and robotic applications. Our final goal is to inspire further discussion in the community about constraint-based QSTR in general, and the possible lines of future research that we outline here in particular.

关键词： Qualitative constraints Spatio-temporal reasoning Just-in-time inference Local consistencies Singleton checks dynamic algorithms Decomposability Adaptivity Parallelization

来源：评论

学校读者我要写书评

暂无评论

Impact of condition number on total sum rate for NOMA systems

引用

ELECTRONICS LETTERS 2020年第20期56卷 1091-+页

作者： Vidal-Beltran, S. Lopez-Bonilla, J. L. Martinez-Pinon, F. Cuenca-Alvarez, R. Inst Politecn Nacl Escuela Super Ingn Mecan & Elect Zacatenco Mexico City DF Mexico Inst Politecn Nacl Ctr Invest & Innovac Tecnol Azcapotzalco Mexico City DF Mexico

In the fifth-generation mobile communications networks, several resource allocation techniques have been used, such as static allocation and dynamic algorithms (greedy or matching theory);this work proposes a new subcarrier allocation scheme based on the evaluation of the instantaneous behaviour of the wireless channel using the condition number of the channel matrix H. Simulation results reveal that the proposed scheme increases the total sum rate of the system, compared to their predecessors.

关键词： wireless channels resource allocation 5G mobile communication multi-access systems greedy algorithms matrix algebra NOMA systems fifth-generation mobile communications networks resource allocation techniques static allocation dynamic algorithms greedy theory matching theory subcarrier allocation scheme instantaneous behaviour wireless channel channel matrix condition number impact

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：