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

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

作者： Blikstad, Joakim Mukhopadhyay, Sagnik Nanongkai, Danupon Tu, Ta-Wei KTH Royal Inst Technol Stockholm Sweden Univ Sheffield Sheffield England Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9781450399135

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with (O) over tilde (k)(n+r root r) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and (O) over tilde hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the (O) over tilde (k)(n root r) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An (O) over tilde (k) (vertical bar E vertical bar + vertical bar V vertical bar root vertical bar V vertical bar)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the (O) over tilde (k) (vertical bar V vertical bar + root vertical bar E vertical bar) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with (O) over tilde (n root r) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple job scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified" algorithm in

关键词： matroid intersection matroid union matroids dynamic algorithms combinatorial optimization spanning tree packing arboricity

来源：评论

学校读者我要写书评

暂无评论

Performance comparison of algorithms for the dynamic shortest path problem

Performance comparison of algorithms for the dynamic shortes...

引用

19th Workshop on Circuits and Systems

作者： Taoka, Satoshi Takafuji, Daisuke Iguchi, Takashi Watanabe, Toshimasa Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan

An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.

关键词： networks shortest paths dynamic algorithms static algorithms computational experiments

来源：评论

学校读者我要写书评

暂无评论

Simple Deterministic algorithms for Fully dynamic Maximal Matching 13

Simple Deterministic Algorithms for Fully Dynamic Maximal Ma...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Neiman, Ofer Solomon, Shay Ben Gurion Univ Negev POB 653 IL-84105 Beer Sheva Israel Weizmann Inst Sci IL-76100 Rehovot Israel

ISBN: (纸本)9781450320290

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst case update time of 0(n). No deterministic algorithm that outperforms the na ve 0(n) one was reported up to this date. The only progress in this direction is due to Ivkovie and Lloyd [14], who in 1993 devised a deterministic algorithm with an amortized update time of 0((n+m) / 2), where m is the number of edges. In this paper we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O(N',1/7). Moreover, our algorithm maintains a matching which is in fact a 3/2 -approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 0 -approximate MCM improving upon the na ve 0(n) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sub -logarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of 0 (log n/ log log n). This result addresses an open question of Onak and Rubinfeld [19]. We also show a deterministic algorithm with optimal space usage of 0(n + m), that for arbitrary graphs maintains a maximal matching with amortized update time of OHI/n,).

关键词： dynamic algorithms maximal matching maximum matching

来源：评论

学校读者我要写书评

暂无评论

Robust Online algorithms for Certain dynamic Packing Problems 1

引用

17th International Workshop on Approximation and Online algorithms (WAOA)

作者： Berndt, Sebastian Dreismann, Valentin Grage, Kilian Jansen, Klaus Knof, Ingmar Univ Kiel Dept Comp Sci Kiel Germany Univ Warwick Coventry W Midlands England

ISBN: (数字)9783030394790

ISBN: (纸本)9783030394790;9783030394783

Online algorithms that allow a small amount of migration or recourse have been intensively studied in the last years. They are essential in the design of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of gamma + epsilon with migration O(1/epsilon), where gamma is the best known offline asymptotic approximation ratio. For our framework, we require only two ingredients: (i) the existence of an online algorithm for the static case (without departures) that provides a provably good solution compared to the total volume of the instance and (ii) that the optimal solution always exceeds this total volume. If these criteria are met, we can complement the online algorithm with any offline algorithm. While these criteria are naturally fulfilled by many dynamic problems, they are especially suited for packing problems. In order to show the usefulness of our approach in this area, we improve upon the best known robust algorithms for the dynamic versions of generalizations of Strip Packing and Bin Packing, including the first robust algorithms for general d-dimensional Bin Packing and Vector Packing.

关键词： Online algorithms dynamic algorithms Competitive ratio Recourse Packing problems

来源：评论

学校读者我要写书评

暂无评论

Semidynamic algorithms for maintaining single-source shortest path trees

引用

ALGORITHMICA 1998年第3期22卷 250-274页

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Matemat Pura & Appl I-67010 Coppito AQ Italy Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We consider the problem of updating a single-source shortest path tree in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph;they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log rr) amortized time per vertex update: where a vertex is considered updated ii it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O(root mlog n) amortized time perverter update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6]. require simple datastructures that are really suitable for a practical and straightforward implementation.

关键词： single-source shortest path dynamic algorithms amortized complexity output complexity

来源：评论

学校读者我要写书评

暂无评论

Simple Deterministic algorithms for Fully dynamic Maximal Matching

引用

ACM TRANSACTIONS ON algorithms 2016年第1期12卷 7-7页

作者： Neiman, Ofer Solomon, Shay Ben Gurion Univ Negev Dept Comp Sci POB 653 IL-84105 Beer Sheva Israel Weizmann Inst Sci IL-76100 Rehovot Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n vertex graphs using a trivial deterministic"algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive 0(n) one was reported up to this date. The only progress in this direction is due to Ivkovie and Lloyd, who in 1993 devised a deterministic algorithm with an amortized update time of 0((n + m)boolean AND 5/2), where m is the number of edges. In this article, we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O(m). Moreover, our algorithm maintains a matching, which in fact is a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 - epsilon)-approximate MCM improving upon the naive 0(n) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sublogarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of 0(logn/ log log n). This result addresses an open question of Onak and Rubinfeld [2010]. We also show a deterministic algorithm with optimal space usage, which for arbitrary graphs maintains a maximal matching in amortized O(m) time and uses only O(n + m) space.

关键词： dynamic algorithms maximal matching maximum matching

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic recognition algorithm and certificate for directed cographs

引用

DISCRETE APPLIED MATHEMATICS 2006年第12期154卷 1722-1741页

作者： Crespelle, C. Paul, C. LIRMM CNRS Dept Informat Montpellier France

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated;otherwise, a certificate is returned within the same complexity. (c) 2006 Elsevier B.V. All rights reserved.

关键词： dynamic algorithms directed cographs certifying algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic Kernels for Hitting Sets and Set Packing

引用

ALGORITHMICA 2022年第11期84卷 3459-3488页

作者： Bannach, Max Heinrich, Zacharias Reischuk, Ruediger Tantau, Till Univ Lubeck Inst Theoret Informat Ratzeburger Allee 160 D-23562 Lubeck Germany

Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k(d) (which is a polynomial as d is a constant), and they do so in time m . 2(d) poly(d) for a small polynomial poly(d) (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k(d) kernel. This paper presents a deterministic solution with worst-case time 3(d) poly(d) for updating the kernel upon inserts and time 5(d) poly(d) for updates upon deletions. These bounds nearly match the time 2(d) poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c(k)) where c = d - 1 + O(1/d) equals the best base known for the static setting.

关键词： Kernelization dynamic algorithms Hitting Set Set Packings

来源：评论

学校读者我要写书评

暂无评论

dynamic matrix rank

引用

THEORETICAL COMPUTER SCIENCE 2009年第41期410卷 4085-4093页

作者： Frandsen, Gudmund Skovbjerg Frandsen, Peter Frands Univ Aarhus Dept Comp Sci DK-8200 Aarhus N Denmark Ramboll Management AS DK-8200 Aarhus N Denmark

We consider maintaining information about the rank of a matrix under changes of the entries. For n x n matrices, we show an upper bound of O(n(1.575)) arithmetic operations and a lower bound of Omega(n) arithmetic operations per element change. The upper bound is valid when changing up to O(n(0.575)) entries in a single Column of the matrix. We also give an algorithm that maintains the rank using O(n(2)) arithmetic operations per rank one update. These bounds appear to be the first nontrivial bounds for the problem. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. The upper bound for element updates uses fast rectangular matrix Multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic Computation of rational functions. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Matrix rank dynamic algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：