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

IEEE INFOCOM Conference

作者： Yang Guo Alexander L. Stolyar Anwar Walid Bell Labs Alcatel-Lucent

ISBN: (纸本)9781467359443

We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem "from scratch". In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified - "more distributed" - version of the Shadow scheme, which performs almost as well in simulations.

关键词： virtual machines shadows dynamic algorithms Allocation Algorithm placement Network routing system parameter

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic algorithms for Maintaining Approximate Shortest Paths Under Deletions 11

Improved Dynamic Algorithms for Maintaining Approximate Shor...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Aaron Bernstein Liam Roditty Department of Computer Science Columbia University Department of Computer Science Bar-Ilan University

ISBN: (纸本)9780898719932

We present the first dynamic shortest paths algorithms that make any progress beyond a long-standing O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas).

关键词： search time shortest path dynamic algorithms algorithms Paths Approximate deletions refresh time Shortest path problem Byways

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic reachability algorithms for directed graphs

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1455-1471页

作者： Roditty, Liam Zwick, Uri Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m root n), and worst-case query time of O(root n). The second is randomized and has an amortized insert/delete time of O(m(0.5)8n) and worst-case query time of O(m(0.43)). This significantly improves the query times of algorithms with similar update times. (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [J. ACM, 28 (1981), pp. 1-4], Italiano [Inform. Process. Lett., 28 (1988), pp. 5-11], Henzinger and King [Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 664-672], and Frigioni et al. [ACM J. Exp. Algorithmics, 6 (2001), (electronic)].

关键词： dynamic algorithms transitive closure strongly connected components

来源：评论

学校读者我要写书评

暂无评论

Recent Advances in Fully dynamic Graph algorithms - A Quick Reference Guide

引用

ACM Journal of Experimental Algorithmics 2022年第11期27卷 1-45页

作者： Hanauer, Kathrin Henzinger, Monika Schulz, Christian Faculty of Computer Science University of Vienna Währinger Str. 29 Vienna Vienna1090 Austria Heidelberg University Im Neuenheimer Feld 205 Baden-Württemberg Heidelberg69120 Germany

In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms. © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： dynamic algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Experimental Analysis of dynamic algorithms for the Single Source Shortest Paths Problem

引用

ACM Journal of Experimental Algorithmics 1998年 3卷 5-5页

作者： Frigioni, Daniele loffreda, Mario Nanni, Umberto Pasqualone, Giulio Univ. di Roma “La Sapienza”

In this paper we propose the first experimental study of the fully dynamic single-source shortest-paths problem on directed graphs with positive real edge weights. In particular, we perform an experimental analysis of three different algorithms: Dijkstra's algorithm, and the two output bounded algorithms proposed by Ramalingam and Reps in [30] and by Frigioni, Marchetti-Spaccamela and Nanni in [18], respectively. The main goal of this paper is to provide a first experimental evidence for: (a) the effectiveness of dynamic algorithms for shortest paths with respect to a traditional static approach to this problem;(b) the validity of the theoretical model of output boundedness to analyze dynamic graph algorithms. Beside random generated graphs, useful to capture the “asymptotic” behavior of the algorithms, we also developed experiments by considering a widely used graph from the real world, i.e., the Internet graph. © 1998, ACM. All rights reserved.

关键词： dynamic algorithms experimental analysis of algorithms shortest paths

来源：评论

学校读者我要写书评

暂无评论

Point enclosure problem for homothetic polygons

引用

THEORETICAL COMPUTER SCIENCE 2025年 1030卷

作者： Akram, Waseem Saxena, Sanjeev Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 India

In this paper, we investigate the following problem: "given a set S of n homothetic polygons, preprocess S to efficiently report all the polygons of S containing a query point." A set of polygons is said to be homothetic if each polygon can be obtained from any other polygon in the set using scaling and translation operations. The problem is a counterpart of the homothetic range search problem discussed by Chazelle and Edelsbrunner (1987) [9]. We show that after preprocessing a set of homothetic polygons with a constant number of vertices, queries can be answered in O (log n + k) optimal time, where k is the output size. The preprocessing takes O(n log n) space and time. We also study the problem in a dynamic setting where insertion and deletion operations are allowed. The results we obtain also hold for c-oriented triangles, where c is a fixed constant.

关键词： Geometric intersection algorithms Data structures dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

A Decremental Algorithm for Fair Buchi Games 22nd

A Decremental Algorithm for Fair Buchi Games

引用

22nd International Symposium on Automated Technology for Verification and Analysis

作者： Saglam, Irmak Schmuck, Anne-Kathrin Tsyrempilon, Munko Max Planck Inst Software Syst MPI SWS Kaiserslautern Germany

ISBN: (纸本)9783031787089;9783031787096

This paper provides the first decremental algorithm for fair Buchi games. It efficiently recalculates the winning region under the deletion of live edges in the underlying game graph. Our algorithm addresses the unique challenges posed by fair Buchi games such as exponential-memory strategies and the non-monotonicity of the winning region under edge deletion. This prevents a straight forward extension of dynamic algorithms from (normal) Buchi games, in particular Jurdzinski's small progress measures, on which these algorithms rely. The main contribution of this paper is the definition of a specialized (one-digit) progress measure for fair Buchi games and its correctness proof. We further derive a decremental algorithm for fair Buchi games using a fixed-point calculation entailed by this progress measure. We show that the (non-optimized) prototype implementation of our decremental algorithm outperforms an (optimized) fair Buchi game solver on a large class of benchmarks. By this, our work not only expands the scope of dynamic algorithms but also underscores the benefit of tailored solutions for specific game structures such as fair Buchi games.

关键词： games on graphs fairness two-player games Buchi games decremental algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic Parameterized Problems and algorithms

引用

ACM TRANSACTIONS ON algorithms 2020年第4期16卷 1–46页

作者： Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Harvard Univ Cambridge MA 02138 USA TU Hamburg Inst Algorithms & Complex D-21071 Hamburg Germany

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n(1+o(1)) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of.(k)n(o(1));such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f (k) log(O(1)) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with n(o(1)) update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k.

关键词： Fixed-parameter algorithms dynamic algorithms cell probe lower bounds

来源：评论

学校读者我要写书评

暂无评论

dynamic Matrix Inverse: Improved algorithms and Matching Conditional Lower Bounds 60

Dynamic Matrix Inverse: Improved Algorithms and Matching Con...

引用

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

来源：评论

学校读者我要写书评

暂无评论

An Analysis of the dynamic Community Detection algorithms in Complex Networks 21

An Analysis of the Dynamic Community Detection Algorithms in...

引用

IEEE International Conference on Industrial Technology (ICIT)

作者： Singh, Dhananjay Kumar Debnath, Narayan C. Haraty, Ramzi A. Choudhury, Prasenjit Natl Inst Technol Durgapur Dept Comp Sci & Engn Durgapur India Eastern Int Univ Sch Comp & Informat Technol Binh Duong Vietnam Lebanese Amer Univ Dept Comp Sci & Math Beirut Lebanon

ISBN: (纸本)9781728157542

Uncovering the dynamics of community structures in complex networks helps us to explore how such community structures change over time. But, understanding these structures is very challenging, especifically in dynamic complex networks where network structure changes frequently and interaction between the individuals changes over time. Recently, many dynamic community detection algorithms have been introduced to capture the dynamics of network community structures. In this paper, we present a detailed analysis of the dynamic community detection algorithms in terms of computation time and accuracy. To provide detailed and extensive analysis, we tested dynamic algorithms on small, medium and large real-world network dataset. Based on the analysis results and network properties, we provide some guidelines that may help to choose the best dynamic community detection algorithms for the given dynamic complex networks.

关键词： complex networks dynamic networks evolving networks temporal networks community structure community detection dynamic community dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：