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

arXiv 2024年

作者： Saxena, Raghuvansh R. Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini Tata Institute of Fundamental Research Maharashtra Mumbai India Department of Computer Science Carnegie Mellon University PittsburghPA United States School of Engineering and Applied Sciences Harvard University CambridgeMA United States Toyota Technological Institute ChicagoIL United States

We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder, Feldman, Seffi, and Schwartz [BFSS15] and Censor-Hillel, Levy, and Shachnai [CLS17], we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O(n1−Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 21. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 12 is impossible without using linear space in adversarially ordered streams Kapralov and Krachun [KK19] and Ω(√n) space in randomly ordered streams, even on bounded degree graphs Kapralov, Khanna, and Sudan [KKS15]. In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing Most Equitable Voting Rules

arXiv

引用

arXiv 2024年

作者： Xia, Lirong Rutgers University-New Brunswick DIMACS United States

How to design fair and (computationally) efficient voting rules is a central challenge in Computational Social Choice. In this paper, we aim at designing efficient algorithms for computing most equitable rules for large classes of preferences and decisions, which optimally satisfy two fundamental fairness/equity axioms: anonymity (every voter being treated equally) and neutrality (every alternative being treated equally). By revealing a natural connection to the graph isomorphism problem and leveraging recent breakthroughs by Babai [2019], we design quasipolynomial-time algorithms that compute most equitable rules with verifications, which also compute verifications about whether anonymity and neutrality are satisfied at the input profile. Further extending this approach, we propose the canonical-labeling tie-breaking, which runs in quasipolynomial-time and optimally breaks ties to preserve anonymity and neutrality. As for the complexity lower bound, we prove that even computing verifications for most equitable rules is GI-complete (i.e., as hard as the graph isomorphism problem), and sometimes GA-complete (i.e., as hard as the graph automorphism problem), for many commonly studied combinations of preferences and decisions. To the best of our knowledge, these are the first problems in computational social choice that are known to be complete in the class GI or GA. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Improving Residential Safety by Multiple Sensors on Multiple Nodes for Joint Emergency Detection

Improving Residential Safety by Multiple Sensors on Multiple...

引用

Conference on Local Computer Networks (LCN)

作者： Artur Sterz Markus Sommer Kevin Lüttge Bernd Freisleben Dept. of Mathematics & Computer Science University of Marburg Germany

ISBN: (数字)9798350388008

ISBN: (纸本)9798350388015

Recent advances in low-cost microcontrollers have enabled innovative smart home applications. However, existing systems typically consist of single-purpose devices that only report sensed data to a controller. Given the potential for residential emergencies, we propose to integrate emergency detection systems into smart home environments. We present an ad-hoc distributed sensor network (DSN) designed to detect five common residential emergencies: fires, gas and water leakages, earthquakes, and intrusions. Our novel approach combines diverse sensors with a voting-based consensus algorithm among multiple nodes, improving accuracy and reliability over traditional alert systems. The consensus algorithm employs a majority rule with weighted votes, allowing adjustments for various scenarios. An experimental evaluation confirms our approach’s effectiveness in accurately detecting emergencies while demonstrating reliability in mitigating node failures, ensuring system longevity, and maintaining robust communication. Additionally, our approach significantly reduces power consumption compared to alternatives.

关键词： Accuracy Power demand Microcontrollers Computer network reliability Earthquakes Smart homes consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast and Simple (1 + Ε)∆-Edge-Coloring of Dense Graphs

arXiv

引用

arXiv 2024年

作者： Dhawan, Abhishek Department of Mathematics University of Illinois at Urbana-Champaign United States

Let Ε ∈ (0, 1) and n, ∆ ∈ N be such that ∆ = Ω (Formula presented). Given an n-vertex m-edge simple graph G of maximum degree ∆, we present a randomized O (m log3 ∆ / Ε2)-time algorithm that computes a proper (1 + Ε)∆-edge-coloring of G with high probability. This improves upon the best known results for a wide range of the parameters Ε, n, and ∆. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Kernelization and Fixed-parameter algorithms for Bicluster Editing

arXiv

引用

arXiv 2024年

作者： Lafond, Manuel Université de Sherbrooke Canada

Given a bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter k, which is the number of allowed modified edges. We first show that one can obtain a kernel with 4.5k vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time O∗(2.581k). Our algorithm has the advantage of being conceptually simple and should be easy to implement. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

A Distributed SOC Balance Control Strategy in the DC Microgrid Based on the Virtual DC Machine Control

A Distributed SOC Balance Control Strategy in the DC Microgr...

引用

International Conference on Information Systems and Computer Aided Education (ICISCAE)

作者： Yiwei Guo Senhao Song Chang Guan Northeast Electric Power University Jilin China

ISBN: (数字)9798350350760

ISBN: (纸本)9798350350777

The virtual DC motor (VDCM) control strategy can simulate the dynamic response of DC motors, enhance system stability and controllability, and has received widespread attention. However, a key challenge in the efficient operation of DC microgrids is the state of charge (SOC) balance of energy storage units, which is crucial for improving the utilization efficiency of energy storage units. This paper introduces an innovative control method that uses VDCM as the basic control layer and combines dynamic consensus algorithm to design SOC balance controller. The proposed method not only maintains the stability of the DC bus voltage, but also achieves SOC consistency among multiple energy storage units. This article validated the effectiveness of the control strategy through a simulation platform built using Matlab/Simulink. The results indicate that the controller can optimize the output of energy storage units, thereby improving the overall efficiency and lifespan of DC microgrid systems.

关键词： Heuristic algorithms Microgrids consensus algorithm Power system stability DC motors Stability analysis State of charge MATLAB Voltage control Energy storage

来源：评论

学校读者我要写书评

暂无评论

A rounding and clustering-based exact algorithm for the p-center problem

arXiv

引用

arXiv 2024年

作者： Ales, Zacharie Duran-Mateluna, Cristian Elloumi, Sourour UMA ENSTA Paris Institut Polytechnique de Paris Palaiseau91120 France CEDRIC Conservatoire National des Arts et Métiers Paris75003 France Chile Faculty of Engineering Industrial Engineering Department Chile

The p-center problem consists in selecting p facilities from a set of possible sites and allocating a set of clients to them in such a way that the maximum distance between a client and the facility to which it is allocated is minimized. This paper proposes a new scalable exact solution algorithm based on client clustering and an iterative distance rounding procedure. The client clustering enables to initialize and update a subset of clients for which the p-center problem is iteratively solved. The rounding drastically reduces the number of distinct distances considered at each iteration. Our algorithm is tested on 396 benchmark instances with up to 1.9 million clients and facilities. We outperform the two state-of-the-art exact methods considered when p is not very small (i.e., p > 5). © 2024, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Ranking and Unranking algorithms for Derangements Based On Lexicographical Order

SSRN

引用

SSRN 2024年

作者： Xie, Zhibo Wu, Ro-Yu Shi, Lingjuan School of Software Northwestern Polytechnical University Shaanxi Xi’an710072 China Department of Industrial Management Lunghwa University of Science and Technology Taoyuan333326 Taiwan

In this paper, we address the derangement problem by constructing a derangement table. We have identified the relationship between lexicographically ordered derangements and their coding trees through the derangement table, and also discovered the connection between the number of derangements and the number of permutations. Based on this derangement table, we have provided relevant formulas and proofs. The paper designs ranking and unranking algorithms for the lexicographical derangement problem using these formulas, with a time complexity of $O(nlogn)$ and a space complexity of $O(n^2)$. According to our investigation, among the existing research, there were no ranking and unranking algorithms for the lexicographical derangement problem with a time complexity of less than or equal to $O(nlogn)$. © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Reducing Diversity to Generate Hierarchical Archetypes

arXiv

引用

arXiv 2024年

作者： Ibias, Alfredo Antona, Hector Ramirez-Miranda, Guillem Guinovart, Enric Alarcon, Eduard Avatar Cognition Barcelona Spain Universitat Politècnica de Catalunya - BarcelonaTech Barcelona Spain

The Artificial Intelligence field seldom address the development of a fundamental building piece: a framework, methodology or algorithm to automatically build hierarchies of abstractions. This is a key requirement in order to build intelligent behaviour, as recent neuroscience studies clearly expose. In this paper we present a primitive-based framework to automatically generate hierarchies of constructive archetypes, as a theory of how to generate hierarchies of abstractions. We assume the existence of a primitive with very specific characteristics, and we develop our framework over it. We prove the effectiveness of our framework through mathematical definitions and proofs. Finally, we give a few insights about potential uses of our framework and the expected results. © 2024, CC BY.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Global Fuzzy Adaptive consensus Control of Unknown Nonlinear Multiagent Systems

引用

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2020年第3期28卷 510-522页

作者： Chen, Jiaxi Li, Junmin Yuan, Xinxin Xidian Univ Sch Math & Stat Xian 710071 Peoples R China

This paper investigates the global consensus problems for the first-order and second-order unknown nonlinear multiagent systems (MASs) with uncertain input disturbance. Fuzzy logic systems are applied to solve the global consensus problem for unknown nonlinear MASs. A fully distributed adaptive fuzzy control is designed to enable followers asymptotically to track the leader without using any dynamics of the leader. The global consensus conditions are also derived for the first-order and second-order unknown MASs, which overcomes the drawback of the semiglobal consensus in existing literature. It is worth mentioning that the proposed approach can greatly alleviate the computation burden because it only needs to update a few parameters. An efficient framework is also given to achieve the global formation control of the second-order unknown nonlinear MAS with an undirected connected graph. Finally, four simulated examples are given to illustrate the effectiveness of the proposed control protocols.

关键词： Protocols Symmetric matrices Artificial neural networks Adaptive control Fuzzy control Uncertainty Adaptive fuzzy control consensus algorithm formation control fuzzy logic systems (FLSs) multiagent systems (MAS)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：