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

Robust Online algorithms for dynamic Choosing Problems 1

17th Conference on Computability in Europe (CiE)

作者： Berndt, Sebastian Grage, Kilian Jansen, Klaus Johannsen, Lukas Kosche, Maria Univ Lubeck D-23562 Lubeck Germany Univ Kiel D-24118 Kiel Germany Gottingen Univ D-37073 Gottingen Germany

ISBN: (数字)9783030800499

ISBN: (纸本)9783030800499;9783030800482

Semi-online algorithms that are allowed to perform a bounded amount of repacking achieve guaranteed good worst-case behaviour in a more realistic setting. Most of the previous works focused on minimization problems that aim to minimize some costs. In this work, we study maximization problems that aim to maximize their profit. We mostly focus on a class of problems that we call choosing problems, where a maximum profit subset of a set objects has to be maintained. Many known problems, such as KNAPSACK, MAXIMUMINDEPENDENTSET and variations of these, are part of this class. We present a framework for choosing problems that allows us to transfer offline ca-approximation algorithms into (alpha - epsilon)-competitive semi-online algorithms with amortized migration O(1/epsilon). Moreover we complement these positive results with lower bounds that show that our results are tight in the sense that no amortized migration of o(1/epsilon) is possible.

关键词： Online algorithms dynamic algorithms Competitive ratio Migration Knapsack Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms via dynamic-Oracle Matroids 2023

Fast Algorithms via Dynamic-Oracle Matroids

引用

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

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Clustering and Diversity Maximization in Doubling Metrics

引用

ACM Transactions on Knowledge Discovery from Data 2025年第4期19卷

作者： Pellizzoni, Paolo Pietracaprina, Andrea Pucci, Geppino Max Planck Institute of Biochemistry Martinsried Germany University of Padova Padova Italy

We present approximation algorithms for some variants of k-center clustering and diversity maximization in a fully dynamic setting, where the active pointset evolves through arbitrary insertions and deletions. All algorithms employ a coreset-based strategy and rely on the use of the cover tree data structure, which we crucially augment to maintain, at any time, some additional information enabling the efficient extraction of the solution for the specific problem. For all the problems under consideration, our algorithms compute (α+ϵ)-approximate solutions, where is the best-known approximation attainable in polynomial time in the standard static setting, and ϵ > 0 is a user-provided accuracy parameter. Remarkably, and unlike previous works, the (cover tree) data structure used by our algorithms and the running times of the update procedures are both independent of the accuracy parameter and, for the k-center variants, also of parameter k. The analysis is performed in terms of the doubling dimension of the metric space which the points belong to, and it shows that, for spaces of bounded doubling dimension, the times required to extract solutions to the above problems are dramatically smaller than those that would be required to recompute solutions on the entire active pointset from scratch. To the best of our knowledge, ours are the first solutions for the matroid center and diversity maximization problems in the fully dynamic setting. The theoretical results are complemented by an extensive set of experiments, which demonstrate the efficiency and effectiveness of our algorithms for k-center without and with outliers against previously known ones. © 2025 Copyright held by the owner/author(s).

关键词： cover tree diversity maximization dynamic algorithms k-center matroid center outliers

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：