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

dynamic normal forms and dynamic characteristic polynomial

THEORETICAL COMPUTER SCIENCE 2011年第16期412卷 1470-1483页

作者： Frandsen, Gudmund Skovbjerg Sankowski, Piotr Univ Aarhus Dept Comp Sci DK-8200 Aarhus N Denmark Warsaw Univ Inst Informat PL-02097 Warsaw Poland Univ Roma La Sapienza Rome Italy

We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n(2) log n) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n(2)k log n) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2(-b) in additional O(n log(2) n log b) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Omega(n(2)) lower bound for rank-one updates and an Omega(n) lower bound for element updates. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Characteristic polynomial Matrix normal form Eigenproblem dynamic algorithm Lower bound

来源：评论

学校读者我要写书评

暂无评论

Efficient and dynamic Double Auctions for Resource Allocation 55

Efficient and Dynamic Double Auctions for Resource Allocatio...

引用

55th IEEE Conference on Decision and Control (CDC)

作者： Zou, Suli Ma, Zhongjing Shao, Yunfeng Ran, Long Liu, Xiangdong Beijing Inst Technol Sch Automat Beijing 100081 Peoples R China State Grid Lvliang Power Supply Co Lvliang 033000 Shanxi Peoples R China State Grid Chongqing Elect Power Co Elect Power Res Inst Chongqing 401123 Peoples R China

ISBN: (纸本)9781509018376

We formulate a class of divisible resource allocation problems among a collection of suppliers and demanders as double-sided auction games. The auction mechanism adopted in this paper inherits some properties of the VCG style auction mechanism, like the incentive compatibility and the efficiency of Nash Equilibrium (NE). In this paper, we propose a novel dynamic process to implement the efficient NE for the underlying auction game. Basically, the double-sided auction game is formulated as a pair of single-sided auction games which are coupled via a joint potential quantity such that the best responses of the players in each single-sided auction and the potential quantity are updated under certain regulations. We introduce a pair of parameters which reveals some rough information related to the valuation or cost functions of players;then, assisted with the given parameters, at each iteration step, a pair of buyer and seller update their best responses under the constrained sets of their bid profiles respectively. We show the advantage of the increase of the potential quantity and individual allocation, and hence the auction game system converges to the efficient NE.

关键词： Divisible resource allocation double-sided auction game dynamic algorithm efficiency Nash equilibrium convergence

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of dynamic Submodular Maximization 2022

On the Complexity of Dynamic Submodular Maximization

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Chen, Xi Peng, Binghui Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781450392648

We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of n insertions and deletions. We show that any algorithm that maintains a (0.5 + epsilon)-approximate solution under a cardinality constraint, for any constant epsilon > 0, must have an amortized query complexity that is polynomial in n. Moreover, a linear amortized query complexity is needed in order to maintain a 0.584-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMN+20, Mon20] that achieve (0.5 - epsilon)-approximation with a polylog(n) amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee 1 - 1/e - epsilon and amortized query complexities O (log(k/epsilon)/epsilon(2)) and k(O(1/epsilon 2)) log n, respectively, where k denotes the cardinality parameter or the rank of the matroid.

关键词： Submodular maximization dynamic algorithm Query complexity

来源：评论

学校读者我要写书评

暂无评论

dynamic Set Cover: Improved algorithms and Lower Bounds 2019

Dynamic Set Cover: Improved Algorithms and Lower Bounds

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Abboud, Amir Addanki, Raghavendra Grandoni, Fabrizio Panigrahi, Debmalya Saha, Barna IBM Almaden Res Ctr San Jose CA 95120 USA Univ Massachusetts Amherst Amherst MA USA IDSIA USI SUPSI Manno Switzerland Duke Univ Durham NC USA

ISBN: (纸本)9781450367059

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1 + epsilon)f-approximation for fully dynamic set cover in O(f(2) log n/epsilon(5)) (amortized) update time, for any epsilon > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f(2)/epsilon(5)), while still obtaining an (1 + epsilon)f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f(2)) in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on f is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of O(f(1-epsilon)) must have an approximation factor that is Omega(n(delta)) for some constant delta > 0 under the Strong Exponential Time Hypothesis.

关键词： dynamic algorithm randomized algorithm set cover competitive ratio

来源：评论

学校读者我要写书评

暂无评论

On dynamic Mapping and Scheduling of Service Function Chains in SDN/NFV-Enabled Networks

On Dynamic Mapping and Scheduling of Service Function Chains...

引用

IEEE Global Communications Conference (IEEE GLOBECOM)

作者： Li, Junling Shi, Weisen Yang, Peng Shen, Xuemin (Sherman) Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada

ISBN: (纸本)9781728109626

Software-defined networking (SDN) and network function virtualization (NFV) together form a promising paradigm that enables the slicing of heterogeneous network resources for agile and efficient service customization. Among other techniques, virtual network function (VNF) mapping and scheduling are crucial to the deployment of SDN/NFV-enabled network services. In this paper, to enhance the performance of service provisioning, dynamic VNF mapping and scheduling are jointly investigated. Specifically, to achieve load balancing with QoS guarantee, we first formulate the VNF mapping and scheduling problem as a mixed integer linear programming (MILP). We then propose a two-stage online algorithm to address the NP-hardness of the MILP. In particular, when new service arrives, we map and schedule the VNFs on a service function chain (SFC) by greedily minimizing the waiting time of VNFs. If the delay requirement cannot be satisfied after the first stage, a delay-aware rescheduling scheme is triggered, in which selected existing VNFs are remapped and rescheduled. The proposed dynamic approach achieves flexible function placement and increases service acceptance ratio. Simulation results are provided to validate the effectiveness of the proposed algorithm.

关键词： NFV SDN VNF mapping VNF scheduling resource allocation dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

dynamic Maxflow via dynamic Interior Point Methods 2023

Dynamic Maxflow via Dynamic Interior Point Methods

引用

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

作者： van den Brand, Jan Liu, Yang P. Sidford, Aaron Georgia Inst Technol Atlanta GA 30332 USA Stanford Univ Stanford CA USA

ISBN: (纸本)9781450399135

In this paper we provide an algorithm for maintaining a (1 - epsilon)-approximate maximum flow in a dynamic, capacitated graph undergoing edge insertions. Over a sequence of m insertions to an n-node graph where every edge has capacity O(poly(m)) our algorithm runs in time (O) over cap (m root n . epsilon(-1)).(1) To obtain this result we design dynamic data structures for the more general problem of detecting when the value of the minimum cost circulation in a dynamic graph undergoing edge insertions achieves value at most F (exactly) for a given threshold F. Over a sequence m insertions to an n-node graph where every edge has capacity O(poly(m)) and cost O(poly(m)) we solve this thresholded minimum cost flow problem in (O) over cap (m root n). Both of our algorithms succeed with high probability against an adaptive adversary. We obtain these results by dynamizing the recent interior point method by [Chen et al. FOCS 2022] used to obtain an almost linear time algorithm for minimum cost flow, and introducing a new dynamic data structure for maintaining minimum ratio cycles in an undirected graph that succeeds with high probability against adaptive adversaries.

关键词： dynamic algorithm graph algorithm maximum flow minimum cost flow bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Maximal Matching in Constant Update Time 57

Fully Dynamic Maximal Matching in Constant Update Time

引用

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

作者： Solomon, Shay Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781509039333

Baswana, Gup ta and Sen [FOCS' 11] showed that fully dynamic maximal matching can be maintained in general graphs with logarithmic amortized update time. More specifically, starting from an empty graph on.. fixed vertices, they devised a randomized algorithm for maintaining maximal matching over any sequence of.. edge insertions and deletions with a total runtime of O(t logn) in expectation and O(t log n + n log(2)n) with high probability. Whether or not this runtime bound can be improved towards O(t) has remained an important open problem. Despite significant research efforts, this question has resisted numerous attempts at resolution even for basic graph families such as forests. In this paper, we resolve the question in the affirmative, by presenting a randomized algorithm for maintaining maximal matching in general graphs with constant amortized update time. The optimal runtime bound O(t) of our algorithm holds both in expectation and with high probability. As an immediate corollary, we can maintain 2-approximate vertex cover with constant amortized update time. This result is essentially the best one can hope for (under the unique games conjecture) in the context of dynamic approximate vertex cover, culminating a long line of research. Our algorithm builds on Baswana et al.'s algorithm, but is inherently different and arguably simpler. As an implication of our simplified approach, the space usage of our algorithm is linear in the (dynamic) graph size, while the space usage of Baswana et al.'s algorithm is always at least Omega(n log n). Finally, we present applications to approximate weighted matchings and to distributed networks.

关键词： dynamic algorithm dynamic matching maximal matching vertex cover

来源：评论

学校读者我要写书评

暂无评论

Deterministic Fully dynamic SSSP and More 64

Deterministic Fully Dynamic SSSP and More

引用

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

作者： van den Brand, Jan Karczmarz, Adam Georgia Inst Technol Atlanta GA USA Univ Warsaw Warsaw Poland IDEAS NCBR Warsaw Poland

ISBN: (纸本)9798350318944

We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and VassilevskaWilliams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known. Our dynamic algorithm works on directed graphs and is deterministic, and can report a single-source shortest paths tree in subquadratic time as well. Thus we also obtain the first deterministic fully dynamic data structure for reachability (transitive closure) with subquadratic update and query time. This answers an open problem of van den Brand, Nanongkai, and Saranurak [FOCS 2019]. Finally, using the same framework we obtain the first fully dynamic data structure maintaining all-pairs (1+ epsilon)-approximate distances within non-trivial sub-n(omega) worst-case update time while supporting optimal-time approximate shortest path reporting at the same time. This data structure is also deterministic and therefore implies the first known non-trivial deterministic worstcase bound for recomputing the transitive closure of a digraph.

关键词： dynamic algorithm single source shortest paths reachability dynamic matrix inverse deterministic

来源：评论

学校读者我要写书评

暂无评论

Group skyline computation

引用

INFORMATION SCIENCES 2012年 188卷 151-169页

作者： Im, Hyeonseung Park, Sungwoo Pohang Univ Sci & Technol POSTECH Pohang South Korea

Given a multi-dimensional dataset of tuples, skyline computation returns a subset of tuples that are not dominated by any other tuples when all dimensions are considered together. Conventional skyline computation, however, is inadequate to answer various queries that need to analyze not just individual tuples of a dataset but also their combinations. In this paper, we study group skyline computation which is based on the notion of dominance relation between groups of the same number of tuples. It determines the dominance relation between two groups by comparing their aggregate values such as sums or averages of elements of individual dimensions, and identifies a set of skyline groups that are not dominated by any other groups. We investigate properties of group skyline computation and develop a group skyline algorithm Gdynamic which is equivalent to a dynamic algorithm that fills a table of skyline groups. Experimental results show that Gdynamic is a practical group skyline algorithm. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Skyline computation dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

L (2,1)-labeling of direct product of paths and cycles

引用

DISCRETE APPLIED MATHEMATICS 2005年第2期145卷 317-325页

作者： Jha, PK Klavzar, S Vesel, A St Cloud State Univ Dept Comp Sci St Cloud MN 56301 USA Univ Maribor Dept Math & Comp Sci PeF SLO-2000 Maribor Slovenia

An L (2, l)-labeling of a graph G is an assignment of labels from {10, 1,..., lambda} to the vertices of G such that vertices at distance two get different labels and adjacent vertices get labels that are at least two apart. The lambda-number lambda(G) of G is the minimum value lambda such that G admits an L (2, 1) -labeling. Let G x H denote the direct product of G and H. We compute the lambda-numbers for each of C7(i) x C7(j), C11(i) x C11(j) x C11(k), P-4 x C-m, and P-5 x C-m. We also show that for n greater than or equal to 6 and m greater than or equal to 7, lambda(P-n x C-m) = 6 if and only if m = 7k, k greater than or equal to 1. The results are partially obtained by a computer search. (C) 2004 Published by Elsevier B.V.

关键词： L(2,1)-labeling vertex labeling lambda-number direct product of graphs rotagraph fasciagraph channel assignment dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：