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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Shay Solomon Amitai Uzrad Tel Aviv University Israel

ISBN: (纸本)9781450399135

The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0. In their pioneering work, Gupta et al. [STOC’17] showed that the greedy algorithm can be dynamized to achieve O(logn)-approximation with update time O(f logn). Building on this result, Hjuler et al. [STACS’18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O(Δ logn) (the analog of O(f logn)), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static lnn-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA’21] and Assadi-Solomon [ESA’21], both with update time O(f2) — exceed the static f-approximation by a factor of (at most) 1+є, for any є > 0. This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static lnn bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+є)lnn for any є > 0, while achieving the same update time (ignoring dependencies on є) of the best previous algorithms (with approximation significantly larger than lnn). Moreover, we prove that the same algorithms achieve O(min{ logn, logC }) amortized recourse; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/C,1].

关键词： dynamic algorithms set cover data structures dominating set

来源：评论

学校读者我要写书评

暂无评论

dynamic Routing and Spectrum Assignment Based on the Consecutive Sub-Channels in Flexible-Grid Optical Networks

引用

IEEE ACCESS 2022年 10卷 128354-128365页

作者： Lohani, Varsha Sharma, Anjali Singh, Yatindra Nath Indian Inst Technol Kanpur Dept Elect Engn Kanpur India

Variable bandwidth channels can be created in Flexible Grid Optical Networks using Optical Orthogonal Frequency Division Multiplexing (O-OFDM). This allows more efficient spectrum use by allocating integral multiple of basic bandwidth slots (sub-channels) to the lightpath requests. In these networks, the constraint of keeping all the allocated slots together is added when deciding routes for the requests. This makes the Routing and Spectrum Assignment (RSA) algorithms in Flexible Grid Optical Networks more challenging. In any network, the lightpath requests will arrive and depart dynamically, leading to spectrum fragmentation. It leads to a reduction of maximum possible utilization as well as an increase in blocking probability. In this paper, we have presented an improvised RSA algorithm using consecutive spectrum slots as an adaptive parameter, that leads to reduced fragmentation. It is evident from the results that the presented RSA algorithm using adaptive parameters reduces the blocking probability and fragmentation more effectively than the shortest path and k-shortest path algorithms reported in the earlier works.

关键词： Routing Optical fiber networks Bandwidth Heuristic algorithms Optical fibers Spread spectrum management Resource management Flexible-grid optical networks routing and spectrum assignment dynamic algorithms fragmentation blocking probability spectrum utilization

来源：评论

学校读者我要写书评

暂无评论

Shortest Path Tree Computation in dynamic Graphs

引用

IEEE TRANSACTIONS ON COMPUTERS 2009年第4期58卷 541-557页

作者： Chan, Edward P. F. Yang, Yaya Univ Waterloo David Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

Let G=(V, E, w) be a simple digraph, in which all edge weights are nonnegative real numbers. Let G' be obtained from G by an application of a set of edge weight updates to G. Let s is an element of V and let T-s and T'(s) be Shortest Path Trees (SPTs) rooted at s in G and G', respectively. The dynamic Shortest Path ( DSP) problem is to compute T'(s) from Ts. Existing work on this problem focuses on either a single edge weight change or multiple edge weight changes in which some of them are incorrect or are not optimized. We correct and extend a few state-of-the-art dynamic SPT algorithms to handle multiple edge weight updates. We prove that these algorithms are correct. dynamic algorithms may not outperform static algorithms all the time. To evaluate the proposed dynamic algorithms, we compare them with the well-known static Dijkstra algorithm. Extensive experiments are conducted with both real-life and artificial data sets. The experimental results suggest the most appropriate algorithms to be used under different circumstances.

关键词： dynamic shortest path shortest path trees dynamic graphs dynamic algorithms graph algorithms routing protocol

来源：评论

学校读者我要写书评

暂无评论

dynamic mechanism design

引用

THEORETICAL COMPUTER SCIENCE 2009年第17期410卷 1564-1572页

作者： Bilo, Davide Guala, Luciano Proietti, Guido ETH Inst Theoret Informat Zurich Switzerland Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Aquila Dipartimento Informat I-67100 Laquila Italy CNR Ist Anal Sistemi & Informat A Ruberti Rome Italy

In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs with selfish edges. More precisely, we are given a graph G of n nodes, and we assume that each edge of G is owned by a selfish agent. The strategy of an agent consists in revealing to the system - at each time instant - the cost at the actual time for using its edge. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how this edge-cost modifications take place, we focus on two settings: (i) the dynamic. in which modifications can happen at any time, and for a given optimization problem on G, the mechanism has to maintain efficiently the output specification and the payment scheme for the agents;(ii) the time-sequenced, in which modifications happens at fixed time steps, and the mechanism has to minimize an objective function which takes into consideration both the quality and the set-up cost of a new solution. In both settings, we investigate the existence of exact and approximate truthful (w.r.t. to suitable equilibrium concepts) mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem. and we show that if edge costs can only decrease and each agent adopts a myopic best response strategy (i.e., its utility is only measured instantaneously), then there exists an efficient dynamic truthful (in myopic best response equilibrium) mechanism for handling a sequence of k declarations of edge-cost reductions having runtime O((h + k) log n), where h is the overall number of payment changes. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Algorithmic mechanism design Truthful mechanisms Approximate mechanisms On-line problems dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

On certificates and lookahead in dynamic graph problems

引用

ALGORITHMICA 1998年第4期21卷 377-394页

作者： Khanna, S Motwani, R Wilson, RH AT&T Bell Labs Dept Fundamental Math Res Murray Hill NJ 07974 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Sandia Natl Labs Intelligent Syst & Robot Ctr Albuquerque NM 87185 USA

Recent work in dynamic graph algorithms has led to efficient algorithms for dynamic undirected graph problems such as connectivity. However, no efficient deterministic algorithms are known for the dynamic versions of fundamental directed graph problems like strong connectivity and transitive closure, as well as some undirected graph problems such as maximum matchings and cuts. We provide some explanation for this lack of success by presenting quadratic lower bounds on the certificate complexity of the seemingly difficult problems, in contrast to the known linear certificate complexity for the problems which have efficient dynamic algorithms. In many applications of dynamic (di)graph problems, a certain form of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases. These give rise to dynamic strong connectivity and dynamic transitive closure problems, respectively. We explain why it is reasonable, and indeed natural and desirable, to assume that lookahead is available in these two applications. Exploiting lookahead to circumvent their inherent complexity, we obtain efficient dynamic algorithms for strong connectivity and transitive closure.

关键词： dynamic algorithms graph algorithms lookahead algorithms graph certificates sparsification strong connectivity transitive closure

来源：评论

学校读者我要写书评

暂无评论

dynamic EUCLIDEAN MINIMUM SPANNING-TREES AND EXTREMA OF BINARY FUNCTIONS

引用

DISCRETE & COMPUTATIONAL GEOMETRY 1995年第1期13卷 111-122页

作者： EPPSTEIN, D University of California

We maintain the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized time O(n1/2 log2 n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in time O(n(epsilon)) per update. Our algorithm uses a novel construction, the ordered nearest neighbor path of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of binary functions, including the diameter of a point set and the bichromatic farthest pair.

关键词： minimum Nearest neighbor update operation extremum values dynamic algorithms Set of points Euclidean binary function Spanning tree deletions

来源：评论

学校读者我要写书评

暂无评论

Enhancing the Computation of Distributed Shortest Paths on Power-law Networks in dynamic Scenarios

引用

THEORY OF COMPUTING SYSTEMS 2015年第2期57卷 444-477页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Romano, Daniele GSSI I-67100 Laquila Italy Univ Laquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy Univ Laquila Dept Ind & Informat Engn & Econ I-67100 Laquila Italy

The problem of finding and keeping updated shortest paths in distributed networks is considered crucial in today's practical applications. In the recent past, there has been a renewed interest in devising new efficient distance-vector algorithms as an attractive alternative to link-state solutions for large-scale Ethernet networks, in which scalability and reliability are key issues or the nodes can have limited storage capabilities. In this paper, we present Distributed Computation Pruning (DCP), a new technique, which can be combined with every distance-vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm and its space occupancy per node. To check its effectiveness, we combined the new technique with DUAL (Diffuse Update ALgorithm), one of the most popular distance-vector algorithm in the literature, which is part of CISCO's widely used EIGRP protocol, and with the recently introduced LFR (Loop Free Routing) which has been shown to have good performances on real networks. We give experimental evidence that these combinations lead to a significant gain both in terms of number of messages sent and of memory requirements per node.

关键词： Design and analysis of algorithms Computer communication networks Distributed algorithms dynamic algorithms Shortest paths Experimental analysis

来源：评论

学校读者我要写书评

暂无评论

Engineering a New Algorithm for Distributed Shortest Paths on dynamic Networks

引用

ALGORITHMICA 2013年第1期66卷 51-86页

作者： Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Maurizio, Vinicio Univ Aquila Dept Elect & Informat Engn I-67100 Laquila Italy MASCOTTE Project I3S CNRS UNSA INRIA F-06902 Sophia Antipolis France

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.

关键词： Shortest paths Distributed networks dynamic algorithms Concurrent update Experimental analysis

来源：评论

学校读者我要写书评

暂无评论

Deterministic dynamic Matching in Worst-Case Update Time

引用

ALGORITHMICA 2023年第12期85卷 3741-3765页

作者： Kiss, Peter Univ Warwick Dept Comp Sci Coventry England

We present deterministic algorithms for maintaining a (3/2 + epsilon) and (2 + epsilon)approximate maximum matching in a fully dynamic graph with worst-case update times (O) over cap (root n) and (O) over cap (1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - delta) (for any delta > 0) and (2 + epsilon) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times O(n(3/4)) and O-epsilon (root n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O-epsilon (root n) and (O) over cap (1) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12-16 July, Glasgow, 2021) respectively. The algorithm achieving (3/2 + epsilon) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a (alpha, delta)-approximate matching sparsifier if at all times H satisfies that mu( H) center dot alpha + delta center dot n >= mu(G) (define (alpha, delta)-approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3/2 + epsilon, delta)-approximate matching sparsifier. We further show how to reduce the maintenance of an a-approximate maximum matching to the maintenance of an (alpha, delta)-approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10-12, 2016). Our reduction requires an update time blow-up

关键词： dynamic algorithms Matching Approximate matching EDCS

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic update of arc-flags

引用

NETWORKS 2014年第3期63卷 243-259页

作者： D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Univ Perugia Dept Math & Informat I-06123 Perugia Italy Univ Pisa Dept Comp Sci I-56127 Pisa Italy Univ Aquila Dept Comp Sci Informat Engn & Math I-67100 Laquila Italy

Best connections in real networks are usually found by applying Dijkstra's shortest paths algorithm. Unfortunately, networks deriving from real-world applications are huge, yielding unsustainable times to compute shortest paths. Therefore, considerable research has been conducted in recent years to accelerate Dijkstra's algorithm on typical instances of transportation and communication networks, such as road networks. These efforts have led to the development of many so called speed-up techniques, as for example Arc-Flags. The main drawback of many of these techniques, including Arc-Flags, is that they do not work well in the realistic dynamic scenarios where the networks change over time. In this article, we introduce a new data structure, named Road-Signs, which is used to update the Arc-Flags of a graph in fully dynamic scenarios. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and does not require large space consumption for sparse networks. We develop a fully dynamic algorithm for updating Arc-Flags, by updating Road-Signs, each time that a modification occurs on an edge of the network. We show that this algorithm is better than recomputation from scratch of Arc-Flags in terms of the affected parameters of the input, which makes this solution suitable to be efficient in practice. However, it is not better than recomputation from scratch in the worst case. We also propose an experimental study to evaluate the practical performance of the new dynamic algorithm. To this aim, we use real-world road networks subject to sequences of weight change operations. Our experiments show a significant speed-up in the updating phase with respect to the recomputation from scratch of *** (c) 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 243-259 2014

关键词： speed-up techniques road networks dynamic algorithms arc-flags shortest paths algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：