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

FrogCOL and FrogMIS: new decentralized algorithms for finding large independent sets in graphs

SWARM INTELLIGENCE 2015年第2-3期9卷 205-227页

作者： Blum, Christian Calvo, Borja Blesa, Maria J. Univ Basque Country UPV EHU San Sebastian Spain Basque Fdn Sci Ikerbasque Bilbao Spain Univ Politecn Cataluna ALBCOM Res Grp Barcelona Spain

Finding large (and generally maximal) independent sets of vertices in a given graph is a fundamental problem in distributed computing. Applications include, for example, facility location and backbone formation in wireless ad hoc networks. In this paper, we study a decentralized (or distributed) algorithm inspired by the calling behavior of male Japanese tree frogs, originally introduced for the graph-coloring problem, for its potential usefulness in the context of finding large independent sets. Moreover, we adapt this algorithm to directly produce maximal independent sets without the necessity of first producing a graph-coloring solution. Both algorithms are compared to a wide range of decentralized algorithms from the literature on a diverse set of benchmark instances for the maximal independent set problem. The results show that both algorithms compare very favorably to their competitors.

关键词： Swarm intelligence Self-desynchronization Maximal independent set decentralized algorithms

来源：评论

学校读者我要写书评

暂无评论

A UNIFIED VIEW OF decentralized algorithms FOR SPARSE LINEAR REGRESSION 9

A UNIFIED VIEW OF DECENTRALIZED ALGORITHMS FOR SPARSE LINEAR...

引用

9th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)

作者： Maros, Marie Scutari, Gesualdo Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA

ISBN: (纸本)9798350344523

We investigate sparse linear regression in high-dimension via the projected LASSO estimator from distributed datasets across a network of agents. This model enables the ambient dimension to scale exponentially with the total sample size. We develop a unified algorithmic framework that encompasses a variety of distributed algorithms, new and old, such as primal, primal-dual, and gradient tracking-based methods, for which we establish both statistical and computational guarantees. Our findings demonstrate that, under standard data generation models, appropriate network connectivity and algorithm tuning, the studied schemes converge to statistically optimal estimates at a linear rate. However, the dependencies of convergence rate on the ambient dimension exhibit a noteworthy difference, ranging from linear to independent scaling. This fact is a new, interesting phenomenon distinctive of the high-dimensional setting and revealed by this study.

关键词： decentralized algorithms linear convergence LASSO estimator mesh networks statistical error

来源：评论

学校读者我要写书评

暂无评论

An efficient communication structure for decentralized algorithms with fault tolerance

引用

COMPUTER SYSTEMS SCIENCE AND ENGINEERING 1997年第6期12卷 343-349页

作者： Yuan, SM Agrawala, AK UNIV MARYLAND DEPT COMP SCICOLLEGE PKMD 20742

decentralized algorithms can be characterized by successive rounds of message interchanges. Several communication structures have been proposed to design decentralized algorithms such as diffusion computations, logically fully connected structures and neighbouring-set communication structures. In this paper, we present a new communication structure, called KDAMS, which can be used to design message and bit optimal decentralized algorithms for evaluating associative and commutative functions which include distributed transaction commitment and extrema finding. In addition, the KDAMS has the potential for easily imposing fault-tolerant mechanisms.

关键词： distributed systems decentralized algorithms fault tolerance consensus protocols message complexity communication structures

来源：评论

学校读者我要写书评

暂无评论

A decentralized Framework for Kernel PCA With Projection Consensus Constraints

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2025年第5期47卷 3908-3921页

作者： He, Fan Yang, Ruikai Shi, Lei Huang, Xiaolin Shanghai Jiao Tong Univ Inst Image Proc & Pattern Recognit MOE Key Lab Syst Control & Informat Proc Shanghai 200240 Peoples R China Fudan Univ Sch Math Sci Shanghai Key Lab Contemporary Appl Math Shanghai 200240 Peoples R China

This paper studies kernel PCA in a decentralized setting, where data are distributively observed with full features in local nodes, and a fusion center is prohibited. Compared with linear PCA, the use of kernel brings challenges to the design of decentralized consensus optimization: the local projection directions are data-dependent. As a result, the consensus constraint in distributed linear PCA is no longer valid. To overcome this problem, we propose a projection consensus constraint and obtain an effective decentralized consensus framework, where local solutions are expected to be the projection of the global solution on the column space of the local dataset. We also derive a fully non-parametric, fast, and convergent algorithm based on the alternative direction method of multiplier, of which each iteration is analytic and communication-efficient. Experiments on a truly parallel architecture are conducted on real-world data, showing that the proposed decentralized algorithm is effective in utilizing information from other nodes and takes great advantages in running time over the central kernel PCA.

关键词： Principal component analysis Kernel Covariance matrices Vectors Optimization Support vector machines Parallel architectures Eigenvalues and eigenfunctions Costs Toy manufacturing industry Kernel methods principal component analysis consensus optimization distributed dataset decentralized algorithms

来源：评论

学校读者我要写书评

暂无评论

Two decentralized heading consensus algorithms for nonlinear multi-agent systems

引用

ASIAN JOURNAL OF CONTROL 2008年第2期10卷 187-200页

作者： Qin Li Jiang, Zhong-Ping Polytech Univ Dept Elect & Comp Engn Brooklyn NY 11201 USA

Inspired by Vicsek's model, in this paper we propose two decentralized heading consensus algorithms for nonlinear multi-agent systems. The first algorithm, called WHCA, can be seen as a weighted Viesek's model. The second algorithm, named LBHCA, is a leader-follower strategy based on the WHCA. It is proved that, under a well-known connectivity assumption, the algorithm WHCA can ensure almost global consensus of the headings, except for the situation where they are initially balanced. For the LBHCA, the global heading consensus is guaranteed under the same connectivity assumption. Simulation results are provided to justify the proposed algorithms.

关键词： decentralized algorithms multi-agent systems consensus Vicsek's model

来源：评论

学校读者我要写书评

暂无评论

QoS provisioning for multiple Femtocells via game theory

引用

COMPUTER NETWORKS 2016年第Jun.19期102卷 70-82页

作者： Sankar, V. Udaya Sharma, Vinod Indian Inst Sci Dept ECE Bangalore 560012 Karnataka India

We consider a system with multiple Femtocells (FCs) operating in a Macrocell. The transmissions in one Femtocell interfere with its neighboring Femtocells. Each Femtocell has multiple users, each requiring a minimum transmission rate. There is also peak transmit power constraint in each channel to control interference to the BS and the users in the Macrocell. We formulate the problem of channel allocation and power control in each Femtocell as a noncooperative Game. We develop efficient decentralized algorithms to obtain a Nash equilibrium (NE) that satisfies the Quality of Service (QoS) of each user, in an efficient way. We also obtain efficient decentralized algorithms to obtain fair NE when it may not be feasible to satisfy the QoS of all the users in FCs. Finally, we extend our algorithms to the case where there may be voice and data users in the system. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Femtocell Cellular communication Power control QoS Game theory decentralized algorithms

来源：评论

学校读者我要写书评

暂无评论

Non-conservative extension of a peer in a P2P inference system

引用

AI COMMUNICATIONS 2009年第4期22卷 211-233页

作者： Abdallah, Nada Goasdoue, Francois Univ Paris Sud F-91893 Orsay France CNRS LRI IASI INRIA Saclay Ile de France GEMO Orsay France

This paper points out that the notion of non-conservative extension of a knowledge base (KB) is important to the distributed logical setting of peer-to-peer inference systems (P2PIS), a.k.a. peer-to-peer semantic systems. It is useful to a peer in order to detect/prevent that a P2PIS corrupts (part of) its knowledge or to learn more about its own application domain from the P2PIS. That notion is all the more important since it has connections with the privacy of a peer within a P2PIS and with the quality of service provided by a P2PIS. We therefore study the following tightly related problems from both the theoretical and decentralized algorithmic perspectives: (i) deciding whether a P2PIS is a conservative extension of a given peer and (ii) computing the witnesses to the corruption of a given peer's KB within a P2PIS so that we can forbid it. We consider here scalable P2PISs that have already proved useful to Artificial Intelligence and DataBases.

关键词： Propositional logic decentralized algorithms consequence finding conservative extension checking

来源：评论

学校读者我要写书评

暂无评论

Distributed Value Function Approximation for Collaborative Multiagent Reinforcement Learning

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第3期8卷 1270-1280页

作者： Stankovic, Milos S. Beko, Marko Stankovic, Srdjan S. Vlatacom Inst Belgrade 11070 Serbia Singidunum Univ Belgrade 11000 Serbia Univ Lisbon Inst Telecomunicacoes Inst Super Tecn P-1649004 Lisbon Portugal Univ Belgrade Sch Elect Engn Belgrade 11000 Serbia Univ Lusofona Humanidades & Tecnol COPELABS P-1749024 Lisbon Portugal

In this article, we propose several novel distributed gradient-based temporal-difference algorithms for multiagent off-policy learning of linear approximation of the value function in Markov decision processes with strict information structure constraints, limiting interagent communications to small neighborhoods. The algorithms are composed of the following: first, local parameter updates based on the single-agent off-policy gradient temporal-difference learning algorithms, including the eligibility traces with state-dependent parameters and, second, linear stochastic time-varying consensus schemes, represented by directed graphs. The proposed algorithms differ in their form, definition of eligibility traces, selection of time scales, and the way of incorporating consensus iterations. The main contribution of this article is a convergence analysis based on the general properties of the underlying Feller-Markov processes and the stochastic time-varying consensus model. We prove under general assumptions that the parameter estimates generated by all the proposed algorithms weakly converge to the corresponding ordinary differential equations with precisely defined invariant sets. It is demonstrated how the adopted methodology can be applied to temporal-difference algorithms under weaker information structure constraints. The variance reduction effect of the proposed algorithms is demonstrated by formulating and analyzing an asymptotic stochastic differential equation. Specific guidelines for the communication network design are provided. The algorithms' superior properties are illustrated by characteristic simulation results.

关键词： Collaborative networks convergence analysis decentralized algorithms distributed consensus multi-agent systems reinforcement learning temporal difference learning value function weak convergence

来源：评论

学校读者我要写书评

暂无评论

decentralized Dynamic Rate and Channel Selection Over a Shared Spectrum

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第6期69卷 3787-3801页

作者： Javanmardi, Alireza Qureshi, Muhammad Anjum Tekin, Cem Bilkent Univ Dept Elect & Elect Engn TR-06800 Ankara Turkey

We consider the problem of distributed dynamic rate and channel selection in a multi-user network, in which each user selects a wireless channel and a modulation and coding scheme (corresponds to a transmission rate) in order to maximize the network throughput. We assume that the users are cooperative, however, there is no coordination and communication among them, and the number of users in the system is unknown. We formulate this problem as a multi-player multi-armed bandit problem and propose a decentralized learning algorithm that performs almost optimal exploration of the transmission rates to learn fast. We prove that the regret of our learning algorithm with respect to the optimal allocation increases logarithmically over rounds with a leading term that is logarithmic in the number of transmission rates. Finally, we compare the performance of our learning algorithm with the state-of-the-art via simulations and show that it substantially improves the throughput and minimizes the number of collisions.

关键词： Throughput Resource management Synchronization Stochastic processes Standards Music Modulation Cognitive radio decentralized algorithms multi-armed bandits regret bounds

来源：评论

学校读者我要写书评

暂无评论

decentralized Learning for Opportunistic Spectrum Access: Multiuser Restless Multiarmed Bandit Formulation

引用

IEEE SYSTEMS JOURNAL 2020年第2期14卷 2485-2496页

作者： Agrawal, Himanshu Asawa, Krishna Jaypee Inst Informat Technol Dept Comp Sci & Engn Noida 201304 India

In opportunistic spectrum access, each secondary user selects a channel from a pool of multiple channels based on their local observations. The challenge here is to learn the best channel in terms of availability, as the channel availability statistics are unknown. In order to learn these unknown statistics, a novel decentralized multiuser learning technique termed as DSEE for channel selection in dynamic networks (DSEE-CSDN) has been proposed. DSEE-CSDN allows secondary users to enter the network during different time slots. Thus, the number of secondary users is not known beforehand. Moreover, the availability status of different independent channels is considered to be changing according to the two-state restless Markov chain model, which, in practice, is more realistic as compared to independent and identically distributed channel state model. Thus, the problem is formulated as a stochastic multiuser restless multiarmed bandit. The proposed algorithm achieves system-wide order-optimal performance under self-play. Results indicate that DSEE-CSDN is able to achieve a logarithmic order of regret. Furthermore, collisions and switching cost are just around 5% and 2% of total time slots, respectively. Also, DSEE-CSDN can achieve probabilistic fairness in channel selection without any preagreement among users.

关键词： Heuristic algorithms Information exchange Markov processes Indexes Quality of service Switches Opportunistic spectrum access (OSA) decentralized algorithms cognitive radio (CR) reinforcement learning restless multiarmed bandits (MABs)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：