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

distributed minimum vertex coloring and maximum independent set in chordal graphs

THEORETICAL COMPUTER SCIENCE 2022年 922卷 486-502页

作者： Konrad, Christian Zamaraev, Viktor Univ Bristol Dept Comp Sci Bristol Avon England Univ Liverpool Dept Comp Sci Liverpool Merseyside England

We give deterministic distributed (1 + epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O(1/epsilon log n) rounds, and our independent set algorithm has a runtime of O(1/epsilon log(1/epsilon) log* n) rounds. For coloring, existing lower bounds imply that the dependencies on E1 and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log 1/epsilon) layers are required as they already contain a large enough independent set. We develop a (1 + epsilon)approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms. (C) 2022 The Authors. Published by Elsevier B.V.

关键词： distributed algorithms Maximum independent set Minimum vertex coloring Approximation algorithms Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

A distributed Model-Free Algorithm for Multi-Hop Ride-Sharing Using Deep Reinforcement Learning

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第7期23卷 8595-8605页

作者： Singh, Ashutosh Al-Abbasi, Abubakr O. Aggarwal, Vaneet Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

The growth of autonomous vehicles, ridesharing systems, and self-driving technology will bring a shift in the way ride hailing platforms plan out their services. However, these advances in technology coupled with road congestion, environmental concerns, fuel usage, vehicles emissions, and the high cost of the vehicle usage have brought more attention to better utilize the use of vehicles and their capacities. In this paper, we propose a novel distributed multi-hop ride-sharing (MHRS) algorithm that uses deep reinforcement learning to learn optimal vehicle dispatch and matching decisions by interacting with the external environment. By allowing customers to transfer between vehicles, i.e., ride with one vehicle for some time and then transfer to another one, MHRS helps in attaining 30% lower cost and 20% more efficient utilization of fleets, as compared to the ride-sharing algorithms. This flexibility of multi-hop feature gives a seamless experience to customers and ride-sharing companies, and thus improves ride-sharing services.

关键词： Multi-hop ride-sharing passenger transfer matching deep Q-network vehicle dispatch distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Network-Slicing-Enabled Computation Offloading in Satellite-Terrestrial Edge Computing Networks: A Bi-Level Game Approach

引用

IEEE INTERNET OF THINGS JOURNAL 2025年第11期12卷 16282-16297页

作者： Wei, Fengsheng Wang, Yatong Feng, Gang Qin, Shuang Univ Elect Sci & Technol China Yangtze Delta Reg Inst Huzhou Huzhou 313001 Peoples R China Beijing Inst Technol Sch Informat & Elect Beijing 100081 Peoples R China Univ Elect Sci & Technol China Natl Key Lab Sci & Technol Commun Chengdu 611731 Peoples R China

Satellite-terrestrial edge computing network (STECN) is emerging as a novel computation paradigm that enables a fashion of on-orbit computation, accommodating real-time processing of various types of computation tasks within a wider area. However, STECNs are incapable of meeting the diverse Quality-of-Service (QoS) requirements of various computational tasks without deploying dedicated infrastructures tailored to each type of task. Therefore, we studied the problem of joint network slicing and task offloading, which is modeled as a problem with a two-layer structure. At the higher level, slice tenants optimize their profits by determining resource allocations from the STECN, while at the lower layer, the users within each network slice maximize their utilities by deciding their offloading policies. In light of the complexity and the intricate interplay of these two problems, a multileader-disjoint-follower bi-level game is proposed. We show that both the leader's game and the followers' game admit at least one Nash equilibrium (NE). We then proposed two distributed algorithms that could prove to converge to the NE of these two games, respectively, without revealing any private information of all stakeholders. We evaluate the performance of our algorithms through extensive simulations, and the results demonstrate that our algorithms converge to the NE rapidly and can achieve superior performance gains compared with some known benchmarks.

关键词： Games Network slicing Satellites Quality of service Computational modeling Low earth orbit satellites Indium phosphide III-V semiconductor materials Edge computing distributed algorithms Bi-level game theory computation offloading network slicing satellite-terrestrial edge computing networks (STECNs)

来源：评论

学校读者我要写书评

暂无评论

The END: Estimation Network Design for Games Under Partial-Decision Information

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2024年第4期11卷 2200-2212页

作者： Bianchi, Mattia Grammatico, Sergio Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands

Multiagent decision problems are typically solved via distributed iterative algorithms, where the agents only communicate among themselves on a peer-to-peer network. Each agent usually maintains a copy of each decision variable, while agreement among the local copies is enforced via consensus protocols. Yet, each agent is often directly influenced by a small portion of the decision variables only: neglecting this sparsity results in redundancy, poor scalability with the network size, and communication and memory overhead. To address these challenges, we develop Estimation Network Design (END), a framework for the design and analysis of distributed algorithms. END algorithms can be tuned to exploit problem-specific sparsity structures, by optimally allocating copies of each variable only to a subset of agents, to improve efficiency and minimize redundancy. We illustrate the END's potential on generalized Nash equilibrium seeking under partial-decision information by designing new algorithms that can leverage the sparsity in cost functions, constraints, and aggregation values, and by relaxing the assumptions on the (directed) communication network postulated in the literature. Finally, we numerically test our methods on a unicast rate allocation problem, revealing greatly reduced communication and memory costs.

关键词： Costs Vectors Games distributed algorithms Scalability Memory management Convergence Nash equilibrium (NE) seeking optimization algorithms variational methods

来源：评论

学校读者我要写书评

暂无评论

Polynomial anonymous dynamic distributed computing without a unique leader

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 37-63页

作者： Kowalski, Dariusz R. Mosteiro, Miguel A. Augusta Univ Sch Comp & Cyber Sci Augusta GA USA SWPS Univ Social Sci & Humanities Warsaw Poland Pace Univ Comp Sci Dept New York NY 10038 USA

Counting the number of nodes in Anonymous Dynamic Networks is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [1], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [2,3]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Anonymous dynamic networks Counting distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully distributed Event-Triggered Optimal Coordinated Control for Multiple Euler-Lagrangian Systems

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第9期52卷 9120-9131页

作者： Huang, Yi Meng, Ziyang Tsinghua Univ Dept Precis Instrument Beijing 100084 Peoples R China

This article studies a fully distributed optimal coordinated control problem with the global cost function for networked Euler-Lagrange (EL) systems subject to unknown model parameters. In particular, the global cost function is the sum of all the local cost functions assigned to each agent and only available to itself. The objective is to minimize the global cost function in a distributed manner while achieving a consensus on its optimal solution. Since the model parameters of the considered EL systems are not available, a new auxiliary system is introduced as a reference model, and its outputs exponentially converge the optimal solution of the global cost function. A fully distributed optimal control algorithm without requiring global information is first proposed. Then, an alternative distributed optimal algorithm via the event-triggered mechanism is proposed to reduce the communication cost. In particular, by combining an edge-based adaptive gain method, the proposed event-triggered optimal algorithm is also fully distributed. Finally, numerical simulation is carried out to validate the theoretical results.

关键词： Cost function Multi-agent systems distributed algorithms Topology Symmetric matrices Optimal control Laplace equations Adaptive gain Euler-Lagrange (EL) systems event-triggered fully distributed control optimal consensus

来源：评论

学校读者我要写书评

暂无评论

Continuous-Time Algorithm Based on Finite-Time Consensus for distributed Constrained Convex Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第5期67卷 2552-2559页

作者： Liu, Hongzhe Zheng, Wei Xing Yu, Wenwu Western Sydney Univ Sch Comp Data & Math Sci Sydney NSW 2751 Australia Southeast Univ Sch Math Nanjing 210096 Peoples R China Southeast Univ Sch Automat Nanjing 210096 Peoples R China

This article studies the convex optimization problem with general constraints, where its global objective function is composed of the sum of local objective functions. The objective is to design a distributed algorithm to cooperatively resolve the optimization problem under the condition that only the information of each node's own local cost function and its neighbors' states can be obtained. To this end, the optimality condition of the researched optimization problem is developed in terms of the saddle point theory. On this basis, the corresponding continuous-time primal-dual algorithm is constructed for the considered constrained convex optimization problem under time-varying undirected and connected graphs. In the case that the parameters involved in the proposed algorithm satisfy certain inequality, the states of all nodes will reach consensus in finite time. Meanwhile, the average state is globally convergent to the optimal solution of the considered optimization problem under some mild and standard assumptions.

关键词： Optimization Convex functions distributed algorithms Convergence Linear programming Multi-agent systems Graph theory distributed optimization finite-time consensus general constraints primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

Communication Optimization for distributed Execution of Graph Neural Networks 37

Communication Optimization for Distributed Execution of Grap...

引用

37th IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Kurt, Sureyya Emre Yan, Jinghua Sukumaran-Rajam, Aravind Pandey, Prashant Sadayappan, P. Univ Utah Kahlert Sch Comp Salt Lake City UT 84112 USA Meta Platforms Menlo Pk CA USA

ISBN: (纸本)9798350337662

Graph Neural Networks (GNNs) have emerged as a very powerful and popular machine learning model for numerous application domains. Each stage of a GNN requires an aggregation (sparse matrix-matrix multiplication) and a linear operation (dense matrix-matrix multiplication). Numerous efforts have addressed the development of distributed implementations for GNNs. Although efficient algorithms for distributed matrix multiplication are well known, the challenge here is the collective optimization of sequences of distributed matrix-matrix multiplications required for GNN, where many degrees of freedom also exist in the ordering of the component matrix-multiplication operations. This paper develops a new approach to distributed GNN, ReDistribution of Matrices (RDM), centered around communication-free distributed matrix-multiplication enabled by matrix redistribution between GNN stages. While the approach is applicable to the numerous algorithmic variants of GNN, the experimental evaluation focuses on GCN (Graph Convolutional Network), including both full-batch training as well as samplingbased training using GraphSAINT. Experimental evaluation with 2-layer and 3-layer GCN, using 128 or 256 hidden features, across eight sparse datasets, on a multi-GPU system with 8 GPUs shows that RDM attains a geometric mean speedup between 2x and 3.7x over two state-of-the-art multi-GPU GCN implementations, CAGNET and DGCL.

关键词： Graph Neural Networks distributed algorithms Multi-GPU GNN Performance Modeling

来源：评论

学校读者我要写书评

暂无评论

Fully distributed real-time voltage control in active distribution networks with large penetration of solar inverters

Fully distributed real-time voltage control in active distri...

引用

IEEE Belgrade PowerTech Conference

作者： Colot, Antonin Stegen, Thomas Cornelusse, Bertrand Univ Liege Dpt Elec Engn & Comp Sci Liege Belgium

ISBN: (纸本)9781665487788

This work addresses voltage regulation problems in low-voltage distribution networks with a large penetration of solar photovoltaic inverters. We propose a fully distributed algorithm that computes solar inverters' active and reactive power setpoints. We consider a convex surrogate of the Branch Flow Model, which is solved iteratively using the Alternating Direction Method of Multipliers (ADMM). Improved voltage regulation is achieved by using local voltage measurements. Only active power curtailment and inverter losses are minimized to maximize the inverter owner's profit. The algorithm is tested on low-voltage (LV) networks with more than 100 buses. This method outperforms a currently implemented scheme in LV networks while showing results close to perfect centralized control.

关键词： active distribution networks volt-var control volt-watt control distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Constrained Optimization With Asynchrony and Delays

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2022年第6期69卷 2772-2776页

作者： Su, Enbing Li, Huaqing Zheng, Zuqing Lu, Qingguo Wang, Zheng Xinzhou Teachers Univ Dept Comp Sci Xinzhou 034000 Peoples R China Southwest Univ Coll Elect & Informat Engn Chongqing Key Lab Nonlinear Circuits & Intelligen Chongqing 400715 Peoples R China Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia

This brief investigates a distributed composite optimization problem over an undirected network with equality constraints. The optimization problem includes a smooth term and two possibly non-smooth terms. Most existing results are devoted to developing distributed algorithms in a synchronous setting with a global clock, where the agents cannot proceed to the next iteration until the slowest agent completes its update. A new asynchronous distributed primal-dual forward-backward splitting algorithm (AD-PDFBS) is presented to solve this problem. Each agent can compute and communicate independently at different times, for different durations, with the information it has even if the latest information from its neighbors is not yet available. The convergence of AD-PDFBS is proved by transforming the asynchronous algorithm into a fixed-point problem utilizing the operator splitting scheme under bounded delay assumption. Experiment result confirms the effectiveness of AD-PDFBS.

关键词： Optimization Convergence Delays distributed algorithms Clocks Communication networks Circuits and systems Asynchronous algorithm primal-dual algorithm forward-backward splitting method non-smooth function delay operator splitting scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：