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

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

来源：评论

学校读者我要写书评

暂无评论

On Regularity Lemma and Barriers in Streaming and dynamic Matching 2023

On Regularity Lemma and Barriers in Streaming and Dynamic Ma...

引用

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

作者： Assadi, Sepehr Behnezhad, Soheil Khanna, Sanjeev Li, Huan Rutgers State Univ New Brunswick NJ 08903 USA Northeastern Univ Boston MA USA Univ Penn Philadelphia PA USA

ISBN: (纸本)9781450399135

We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs: (i) A deterministic single-pass streaming algorithm that finds a (1 - o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. (ii) A randomized fully dynamic algorithm that with high probability maintains a (1 - o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log* n)T(1) factor. Nevertheless, in each case, they show that the "right" answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemeredi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

关键词： Maximum Matching Streaming algorithms dynamic algorithms Regularity Lemma

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance in the Fully dynamic Model 64

Approximating Edit Distance in the Fully Dynamic Model

引用

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

作者： Kociumaka, Tomasz Mukherjee, Anish Saha, Barna Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Univ Warwick Coventry W Midlands England Univ Calif Dept Comp Sci & Engn San Diego CA USA

ISBN: (纸本)9798350318944

The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. Given two strings of length at most n, a simple dynamic programming computes their edit distance exactly in O(n(2)) time, which is also the best possible (up to subpolynomial factors) assuming the Strong Exponential Time Hypothesis (SETH). The last few decades have seen tremendous progress in edit distance approximation, where the runtime has been brought down to subquadratic, to near-linear, and even to sublinear at the cost of approximation. In this paper, we study the dynamic edit distance problem where the strings change dynamically as the characters are substituted, inserted, or deleted over time. Each change may happen at any location of either of the two strings. The goal is to maintain the (exact or approximate) edit distance of such dynamic strings while minimizing the update time. The exact edit distance can be maintained in O(n log(2) n) time per update (Charalampopoulos, Kociumaka, Mozes;2020), which is again tight assuming SETH. Unfortunately, even with the unprecedented progress in edit distance approximation in the static setting, strikingly little is known regarding dynamic edit distance approximation. Utilizing the best near-linear-time (Andoni, Nosatzki;2020) and sublinear-time (Goldenberg, Kociumaka, Krauthgamer, Saha;2022) approximation algorithm, an old exact algorithm (Landau and Vishkin;1988), and a generic dynamic strings implementation (Mehlhorn, Sundar, Uhrig;1996), it is possible to achieve an O(n(c))-approximation in n(0.5-c+o(1)) update time for any constant c is an element of [0, 1/6]. Improving upon this trade-off, characterized by the approximation-ratio and update-time product n(0.5+o(1)), remains wide open. The contribution of this work is a dynamic n(o(1))-approximation algorithm with amortized expected update time of n(o(1)). In other w

关键词： edit distance dynamic algorithms approximation

来源：评论

学校读者我要写书评

暂无评论

New Partitioning Techniques and Faster algorithms for Approximate Interval Scheduling

引用

ALGORITHMICA 2024年第9期86卷 2997-3026页

作者： Compton, Spencer Mitrovic, Slobodan Rubinfeld, Ronitt Stanford Univ Comp Sci Dept 353 Jane Stanford Way Stanford CA 94305 USA Univ Calif Davis Comp Sci Dept Kemper Hall Davis CA 95616 USA MIT CSAIL 32 Vassar St Cambridge MA 02139 USA

Interval scheduling is a basic algorithmic problem and a classical task in combinatorial optimization. We develop techniques for partitioning and grouping jobs based on their starting/ending times, enabling us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in a dynamic setting produces several new results. For (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+\varepsilon )$$\end{document}-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O(logn epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\nicefrac {\log {n}}{\varepsilon })$$\end{document} update and O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log {n})$$\end{document} query worst-case time. Our techniques are also applicable in a setting where jobs have weights. We design a fully dynamic deterministic algorithm whose worst-case update and query times are poly(logn,1 epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {poly} (\log n,\frac{1}{\varepsilon })$$\end{document}. This is the first algorithm that maintains a (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath

关键词： Interval scheduling Job scheduling dynamic algorithms Local computation algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time 64

Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear ...

引用

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

作者： Bhattacharya, Sayan Kiss, Peter Saranurak, Thatchaphol Univ Warwick Coventry W Midlands England Univ Michighan Ann Arbor MI USA

ISBN: (纸本)9798350318944

We show a fully dynamic algorithm for maintaining (1 + epsilon)-approximate size of maximum matching of the graph with n vertices and m edges using m(0.5-Omega epsilon(1)) update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16], [Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for (1, epsilon n)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.

关键词： Approximate Maximum Matching dynamic algorithms Sublinear Algorithm

来源：评论

学校读者我要写书评

暂无评论

The Complexity of dynamic Least-Squares Regression 64

The Complexity of Dynamic Least-Squares Regression

引用

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

作者： Jiang, Shunhua Peng, Binghui Weinstein, Omri Columbia Univ Dept Comp Sci New York NY 10027 USA Hebrew Univ Jerusalem Dept Comp Sci Jerusalem Israel

ISBN: (纸本)9798350318944

We settle the complexity of dynamic least-squares regression (LSR), where rows and labels (A((t)), b((t))) can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an epsilon-approximate solution to min(x(t)) parallel to A((t)) x((t)) - b((t))parallel to(2) for all t is an element of [T]. We prove sharp separations (d(2-o(1)) vs. similar to d) between the amortized update time of: (i) Fully vs. Partially dynamic 0.01-LSR;(ii) High vs. low-accuracy LSR in the partially-dynamic (insertion-only) setting. Our lower bounds follow from a gap-amplification reduction-reminiscent of iterative refinement-from the exact version of the Online Matrix Vector Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where the i-th online product Hv((i)) only needs to be computed to 0.1-relative error. All previous fine-grained reductions from OMv to its approximate versions only show hardness for inverse polynomial approximation epsilon = n(-omega(1)) (additive or multiplicative). This result is of independent interest in fine-grained complexity and for the investigation of the OMv Conjecture, which is still widely open.

关键词： Numerical linear algebra dynamic algorithms fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

dynamic treewidth 64

Dynamic treewidth

引用

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

作者： Korhonen, Tuukka Majewski, Konrad Nadara, Wojciech Pilipczuk, Michal Sokolowski, Marek Univ Bergen Dept Informat Bergen Norway Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9798350318944

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most 6k + 5 under the promise that the treewidth of G never grows above k. The amortized update time is O-k(2(root log n log log n)), where n is the vertex count of G and the O-k(.) notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle's Theorem: for any fixed property phi expressible in the CMSO2 logic, the data structure can maintain whether G satisfies phi within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

关键词： treewidth parameterized algorithms dynamic algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2014年第2期47卷 240-247页

作者： Chan, Timothy M. Pathak, Vinayak Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

At SODA'1 0, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + root 3)/2 + epsilon approximate to 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + root 2)/2 approximate to 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Streaming algorithms dynamic algorithms High dimension

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic Colouring of Sparse Graphs 2023

Improved Dynamic Colouring of Sparse Graphs

引用

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

作者： Christiansen, Aleksander Bjorn Grodt Nowicki, Krzysztof Rotenberg, Eva Tech Univ Denmark Lyngby Denmark Univ Copenhagen Copenhagen Denmark Pathway Com Krakow Poland

ISBN: (纸本)9781450399135

Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are computable upon query time. We give a deterministic algorithm that uses O(alpha(2)) colours for a dynamic graph of arboricity alpha, and a randomised algorithm that uses O(min{alpha log alpha, alpha log log log n}) colours in the oblivious adversary model. Our deterministic algorithm has update- and query times polynomial in alpha and log n, and our randomised algorithm has amortised update- and query time that with high probability is polynomial in log n with no dependency on the arboricity. Thus, we improve the number of colours exponentially compared to the state-of-the art for implicit colouring, namely from O(2(alpha)) colours, and we approach the theoretical lower bound of Omega(alpha) for this arboricity-parameterised approach. Simultaneously, our randomised algorithm improves the update- and query time to run in time solely polynomial in log n with no dependency on alpha. Our algorithms are fully adaptive to the current value of the dynamic arboricity at query or update time.

关键词： dynamic algorithms graph colouring arboricity

来源：评论

学校读者我要写书评

暂无评论

Top-k Distance Queries on Large Time-Evolving Graphs

引用

IEEE ACCESS 2023年 11卷 102228-102242页

作者： D'Ascenzo, Andrea D'Emidio, Mattia Univ Aquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy

Fast extraction of top- k distances from graph data is a primitive of paramount importance in the fields of data mining, network analytics and machine learning, where ranked distances are exploited for several purposes (e.g., link prediction or network classification). While investigation on computational methods to address this retrieval task for regularly sized, static inputs has been extensive, much less is known when managed graphs are massive, i.e., having millions of vertices/edges, and time-evolving, i.e., when their structure can grow over time, a scenario that introduces a number of scalability and effectiveness issues otherwise not arising. Since, nowadays, most real-world applications exploiting top- k distances have to handle inherently dynamic and rapidly growing graphs, in this paper we present the first dynamic indexing scheme that supports very fast queries on top- k distances when graphs are massive and incrementally time-evolving. We assess the scalability and effectiveness of our method through extensive experimentation on both real-world and artificial graph datasets.

关键词： Heuristic algorithms Data structures Scalability Data mining Labeling Computational modeling Time complexity Algorithm design and analysis Algorithm engineering dynamic algorithms k shortest distances massive graph mining

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：