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

Sensitivity, Proximity and FPT algorithms for Exact Matroid Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Eisenbrand, Friedrich Rohwedder, Lars Węgrzycki, Karol EPFL Lausanne Switzerland Maastricht University Maastricht Netherlands Saarland University Max Planck Institute for Informatics Saarbrücken Germany

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from {−∆, . . ., ∆} or more generally m-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by ∆ and m for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in {0, 1}, or arbitrary ∆ and m = 1. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. © 2024, CC0.

关键词： consensus algorithm

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ghaffari, Mohsen Trygub, Anton MIT United States

We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy. The general approach we take along the way to this result can be viewed as a novel adaptation of Dijkstra’s classic approach to SSSP, which makes it suitable for the distributed setting. Notice that Dijkstra’s algorithm itself is not efficient in the distributed setting due to its need for repeatedly computing the minimum-distance unvisited node in the entire network. Our adapted approach has other implications, as we outline next. As a step toward the above end-result, we obtain a simple deterministic algorithm for exact SSSP with near-optimal time and message complexities of Õ(n) and Õ(m), in which each edge communicates only poly(log n) messages. Therefore, one can simultaneously run n instances of it for n sources, using a simple random delay scheduling. That computes All Pairs Shortest Paths (APSP) in the near-optimal time complexity of Õ(n). This algorithm matches the complexity of the recent APSP algorithm of Bernstein and Nanongkai [STOC 2019] using a completely different method (and one that is more modular, in the sense that the SSSPs are solved independently). It also takes a step toward resolving the open problem on a deterministic Õ(n)-time APSP, as the only randomness used now is in the scheduling. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Research on Travel Route Planing Problem Based on Greedy algorithm

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Yiquan College of Mathematics and System Science Xinjiang University Urumqi China Shenzhen X-institute Shenzhen China

The greedy algorithm based route planning problem is a method of finding the optimal or near optimal route between a given starting and ending point. This article first uses PCA method to reduce the dimensionality of urban evaluation indicators, extracts key principal components, and KMO and TOPSIS algorithms to reduce the dimensionality of the data. Secondly, for datasets that have not passed the KMO test, a comprehensive evaluation will be conducted using the entropy weight method and TOPSIS method. Finally, based on the greedy algorithm, a route planning algorithm was proposed and optimized to provide personalized route customization according to the different needs of tourists. We also took into account the local travel efficiency, the time required to visit tourist attractions, and necessary daily rest time to reduce costs and avoid falling into the local optimal solution. © 2024, CC BY-NC-SA.

关键词： consensus algorithm

Two-Step Blackout Mitigation by Flexibility-Enabled Microgrid Islanding 24

学校读者我要写书评

暂无评论

Two-Step Blackout Mitigation by Flexibility-Enabled Microgri...

Proceedings of the 15th ACM International Conference on Future and Sustainable Energy Systems

作者： Philipp Danner Anna Volkova Hermann De Meer University of Passau Germany

ISBN: (纸本)9798400704802

Blackouts are disastrous events with a low probability of occurrence but a high impact on the system and its users. With the help of more distributed and controllable generation and sector-coupled flexibility, microgrids could be prepared to operate in islanded mode during a blackout. This paper discusses a two-step blackout mitigation approach for highly renewable microgrids that utilizes user flexibility and energy storage systems for power balance in islanded grid operation. The proposed method includes a proactive flexibility reservation step, which derives a minimal reservation schedule for microgrid resources under uncertainty considering related operational costs. As a second step, during a blackout, a fully distributed control is implemented to maximize the usage of available resources based on a sequence of max and min-consensus rounds. This paper focuses on the second step, for which the effectiveness of blackstart and long-term coordination is shown. Load shedding can be reduced by 40% compared to the forecast value. A hardware-in-the-loop simulation of a grid-forming converter further showed a fast convergence toward the optimal operation point.

关键词： consensus algorithm microgrid islanding

PUF-Based Authentication System with Resilience against Multi-Faceted Attacks for Blockchain-based IoT Networks

学校读者我要写书评

暂无评论

PUF-Based Authentication System with Resilience against Mult...

Applied Intelligence and Computing (AIC), IEEE World Conference on

作者： Anindita Sarkar Souvik Ganguly Partha Sarathi Sarkar Swagata Roy Chatterjee Department of Electronics and Communication Engineering Netaji Subhash Engineering College Kolkata India

ISBN: (数字)9798350384598

ISBN: (纸本)9798350384604

Now a days, blockchain based IOT networks are gaining popularity for the unlimited space and robust security mechanism. Blockchain is the best solution for the IoT devices to store the huge amount of data generated by them with utmost privacy and security using distributed ledger. However, the resource constrained IoT devices having low computing power are unable to meet the huge computing requirements of data mining in blockchain networks. This paper has proposed a robust Physically Unclonable Function (PUF)-based authentication system to replace the popular consensus algorithms by a lightweight hardware-based authentication mechanism without compromising the security and privacy. The proposed ring oscillator based PUF modules fortify users' credentials and withstand various types of attacks in decentralized and tamper-resistant blockchain based IOT network with significant reduction in latency and power consumption. Attack analysis is done to compare the vulnerabilities of both the proposed and conventional systems to prominent blockchain attacks. The results of attack analysis demonstrate that the proposed system outperforms the conventional PoW system.

关键词： Power demand Dictionaries System performance Authentication consensus algorithm Vectors Blockchains Internet of Things Security Resilience

Blockchain-Enabled Parallel Learning in Industrial Edge-Cloud Network: a Fuzzy DPoSt-PBFT Approach

学校读者我要写书评

暂无评论

Blockchain-Enabled Parallel Learning in Industrial Edge-Clou...

IEEE Globecom Workshops

作者： Fan Yang Jianwei Tian Tao Feng Fangmin Xu Chao Qiu Chenglin Zhao School of Information and Communication Engineering (SICE) Beijing University of Posts and Telecommunications (BUPT) Beijing China State Grid Hunan Electric Power Company Limited China National Tendering Center of Mach. Elec. Equipment MIIT College of Intelligence and Computing Tianjin University

ISBN: (纸本)9781665423915

Recently, parallel reinforcement learning (PRL) based Industrial Internet of Things (IIoT) edge-cloud resource scheduling has elicited escalating attention. However, with the scale of IIoT expands, there are several challenges in the existing researches: 1) large number of parallel servers slows down the convergence rate of PRL; 2) malicious parallel server affects resource allocation efficiency. In order to solve the above efficiency and security problem, blockchain-based approaches are introduced in PRL based resource allocation problem. However, traditional consensus algorithm in blockchain is not suitable for resource allocation and is inefficient. Thus, in this article, based on a novel fuzzy delegated proof of state and practical byzantine fault tolerance (fuzzy DPoSt+PBFT) consensus algorithm, we propose a blockchain-enabled collaborative parallel Q-learning (CPQL) approach to address the above challenges. To be specific, we first construct an edge-cloud collaborative architecture for executing the diversity intelligence IIoT applications. Then, we propose a CPQL algorithm for edge-cloud resource allocation and choosing the optimal number of parallel edge servers to speed up the Q-table training. In the Q-table aggregation process in CPQL, a fuzzy DPoSt+PBFT algorithm is designed for secure CPQL training and efficient consensus. Experimental results show the superior performance of the proposed approach. And the proposed approach has great potential in IIoT resource allocation problem.

关键词： Training Q-learning Job shop scheduling Fault tolerant systems Collaboration consensus algorithm Resource management

On the Hypomonotone Class of Variational Inequalities

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Alomar, Khaled Chavdarova, Tatjana CISPA Helmholtz Center for Information Security Germany Politecnico di Milano University of California Berkeley United States

This paper studies the behavior of the extragradient algorithm [Korpelevich, 1976] when applied to hypomonotone operators, a class of problems that extends beyond the classical monotone setting. To support the understanding of this variational inequality problem class, we focus on a subclass of hypomonotone linear operators, characterizing them based on their eigenvalues and providing concrete examples. While the extragradient method is widely recognized for its efficiency in solving variational inequalities involving monotone and Lipschitz continuous operators, we demonstrate that it does not guarantee convergence in the hypomonotone case. In particular, we construct a counterexample where the extragradient method diverges regardless of the step size. A numerical experiment is presented to support this result. © 2024, CC BY.

关键词： consensus algorithm

Analysis of Effects of Communication Conditions on Distributed Secondary Control for DC Microgrids

学校读者我要写书评

暂无评论

Analysis of Effects of Communication Conditions on Distribut...

International Conference on Power Electronics and Motion Control (IPEMC)

作者： Run Li Sucheng Liu Mengyu Xia Xiaodong Liu Anhui Province Key Laboratory of Power Electronics and Motion Control Anhui University of Technology Ma’anshan China

ISBN: (数字)9781728153018

ISBN: (纸本)9781728153025

Distributed control strategies based on consensus algorithms for DC microgrids have gained intensive interest in recent years thanks to its advantages of high reliability, resilience, and expandability, over centralized control ones. Thus, global information can be accurately shared in a distributed way by sharing information between neighbor units. Meanwhile, hierarchical control paradigm consisting of three levels, i.e., primary, secondary, and tertiary, has become a standard solution for DC microgrids. Usually, the primary control is performed locally without communication, while secondary and tertiary controls desire distributed communication to obtain average voltage or current among units. Thus, the sparse communications are crucial to distributed control of DC microgrids. In this work, three main communication conditions, i.e., link failure, communication delay, and noise are included in analyzing effects of these conditions on distributed control of DC microgrids. Simulation model is built to verify the analysis in MATLAB/Simulink environment.

关键词： Analytical models Decentralized control Microgrids consensus algorithm Steady-state Delays Voltage control

Surplus-Based ADMM for Distributed Constrained Optimization over Directed Graphs

学校读者我要写书评

暂无评论

Surplus-Based ADMM for Distributed Constrained Optimization ...

IEEE Conference on Decision and Control

作者： Qiutong Ji Guanghui Wen Tao Yang School of Cyber Science and Engineering Southeast University Nanjing China Department of Systems Science School of Mathematics Southeast University Nanjing China State Key Laboratory of Synthetical Automation for Process Industries Northeastern University Shenyang China

ISBN: (数字)9798350316339

ISBN: (纸本)9798350316346

This paper introduces a distributed parallel Alternating Direction Method of Multipliers (ADMM) algorithm for solving the distributed constrained optimization problem over directed graphs. To effectively handle the effect of asymmetric information communication on the convergence of the optimization algorithm, a surplus-based averaging consensus algorithm is integrated into the ADMM-based optimization algorithm. Unlike existing distributed ADMM algorithms over directed graphs that focus on the case with solely local constraints, the proposed algorithm can deal with both local constraints and coupling constraints. Under the assumption that the objective function is convex and the underlying graph is strongly connected, the convergence of the surplus-based ADMM to an optimal solution of the distributed constrained problem is proved. Finally, numerical simulations are conducted to validate the effectiveness of the proposed algorithm.

关键词： Couplings Directed graphs consensus algorithm Linear programming Numerical simulation Convex functions Optimization Convergence