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

Lyapunov-based real-time optimization method in microgrids: A comprehensive review

RENEWABLE & SUSTAINABLE ENERGY REVIEWS 2025年 213卷

作者： Alilou, Masoud Shotorbani, Amin Mohammadpour Mohammadi-Ivatloo, Behnam Urmia Univ Technol Engn Fac Khoy Dept Elect Engn Orumiyeh Iran Univ British Columbia Sch Engn Kelowna BC Canada LUT Univ Sch Energy Syst Dept Elect Engn Lappeenranta Finland

An effective energy management system in a microgrid is of paramount importance, optimizing local energy utilization for diverse consumer needs. Prevalent strategies often rely on offline day-ahead or two-stage methods, assuming stable microgrid configurations or precise forecasts-a challenge in practical operations. A real-time energy management system approach struggles to achieve global optimal solutions, though inherently providing robustness against forecast uncertainties. A recent and promising approach is applying the Lyapunov optimization method, known for online optimization, to address challenges in real-time microgrid energy management systems. This paper provides a comprehensive exploration of Lyapunov-based real-time energy management systems in microgrids. We begin by elucidating the integration of the Lyapunov method into microgrid energy management. Categorizing pertinent research papers systematically, we differentiate parameters such as microgrid components with respect to real-time energy management systems, objective functions, and designs of the Lyapunov algorithm, covering establishment of virtual queues, drift-plus-penalty, and the control parameter roles of the algorithm. Integral to our investigation is a thorough assessment of the efficacy of the Lyapunov method in real-time microgrid energy management. The analysis highlights the efficacy of Lyapunov optimization in microgrid energy management system operation and underscores it as a solution to realtime energy management system challenges in microgrids, establishing its merits and applicability in scholarly and practical contexts.

关键词： Energy management Microgrid online algorithms Real-time Lyapunov optimization Virtual queue

来源：评论

学校读者我要写书评

暂无评论

Correlation clustering algorithm for dynamic complete signed graphs: an index-based approach

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2025年 1-20页

作者： Shakiba, Ali Univ New South Wales Sydney Australia

This paper presents a novel index-based approach to improve the runtime and extend the applicability of approximation algorithms for correlation clustering on complete signed graphs. Building on prior work, we introduce an indexing structure that enhances runtime efficiency and enables full dynamic updates, including vertex addition, removal, and edge sign flipping. For a complete graph with n vertices and m positively signed edges, our method achieves an amortized runtime of O(malpha(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(m \cdot \alpha (n))$$\end{document} for dynamic operations and O(m+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(m + n)$$\end{document} for clustering queries with a fixed threshold epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}, while pre-computation scales as O(m(alpha(G)+logm))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(m \cdot (\alpha (G) + \log m))$$\end{document} where alpha(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha

关键词： Correlation clustering Dynamic graphs online algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive perimeter defense in linear environments

引用

THEORETICAL COMPUTER SCIENCE 2025年 1043卷

作者： Bajaj, Shivam Torng, Eric Bopardikar, Shaunak D. Purdue Univ Dept Elect & Comp Engn W Lafayette IN 47907 USA Michigan State Univ Dept Comp Sci & Engn E Lansing MI USA Michigan State Univ Dept Elect & Comp Engn E Lansing MI USA

We address a perimeter defense problem in which a single mobile defender defends specified points of interest in a given region (perimeter) from intruders moving with fixed speed and direction in a linear environment. The problem is parameterized by 1) the perimeter size and 2) the intruder-to-defender speed ratio. We consider two scenarios: (i) intruders move inward, i.e., towards the midpoint (referred to as the origin) of the environment, to reach the perimeter;and, (ii) intruders move outward, i.e., away from the midpoint, to reach the perimeter. We first establish necessary conditions on the problem parameters for which any online algorithm can have finite competitiveness. We also establish conditions for which no algorithm can be better than 2competitive. We then design three classes of online algorithms and establish the competitiveness of each algorithm in both scenarios by characterizing corresponding sufficient conditions in the above parameter regime.

关键词： Perimeter defense Competitive analysis Dynamic vehicle routing online algorithms

来源：评论

学校读者我要写书评

暂无评论

online kernel-based clustering

引用

PATTERN RECOGNITION 2025年 158卷

作者： Alam, Abrar Malhotra, Akshay Schizas, Ioannis D. Univ Texas Arlington Dept EE Arlington TX 76019 USA InterDigital Commun Inc Los Altos CA 94022 USA US Army Combat Capabil Dev Command Army Res Lab Aberdeen Proving Ground MD 21005 USA

A novel online joint kernel learning and clustering (OKC) framework is derived which is capable of determining time-varying clustering configurations without the need for training data. To facilitate clustering via sparse kernel factorization, a novel time-dependent metric is devised to quantify closeness of candidate kernel similarity matrices to a block diagonal structure. The task is later performed online as newly acquired data are processed making it appropriate for non-stationary settings. The necessary minimization to carry out kernel learning and clustering is performed via an effective interplay among block coordinate descent, difference of convex functions minimization and projected subgradient descent which results in an online iterative algorithm that updates online the kernel covariance matrix, as well as the associated clustering configuration. The resulting recursive kernel updates are proved to converge to a bounded limit. Detailed numerical examples utilizing both synthetic and real data show the superior clustering accuracy achieved by the novel approach over existing alternatives while requiring considerably less running time.

关键词： Kernel learning online algorithms Clustering Optimization

来源：评论

学校读者我要写书评

暂无评论

Optimal Publishing Strategies on a Base Layer 28th

Optimal Publishing Strategies on a Base Layer

引用

28th International Conference on Financial Cryptography and Data Security

作者： Bar-On, Yogev Mansour, Yishay Tel Aviv Univ Tel Aviv Israel Google Res Tel Aviv Israel

ISBN: (纸本)9783031786754;9783031786761

A growing number of products use layer 2 solutions to expand the capabilities of primary blockchains like Ethereum, where computation is off-loaded from the root chain, and the results are published to it in bulk. Those include optimistic and zero-knowledge rollups, information oracles, and app-specific chains. This work presents an analysis of layer 2 blockchain strategies determining the optimal times for publishing transactions on the root chain. There is a trade-off between waiting for a better layer 1 gas price and the urgency to finalize layer 2 transactions. We present a model for the problem that captures this trade-off, generalizing previous works, and we analyze the properties of optimal publishing strategies. We show that such optimal strategies hold a computable simple form for a large class of cost functions.

关键词： Blockchain Layer 2 Rollup online algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive online Stay-or-Switch algorithms With Minimum Commitment and Switching Cost

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2022年第6期30卷 2804-2817页

作者： Shen, Zhirong Zhang, Guanglin Donghua Univ Coll Informat Sci andTechnol Shanghai 201620 Peoples R China

In this paper, we consider an online decision problem, where a decision maker has an option to buy a discount plan for his/her regular expenses. The discount plan costs an immediate upfront charge plus a commitment charge per time slot. Upon expiration, the discount period can be extended if the decision maker continues paying the commitment charge, or be canceled if he or she decides not to pay the commitment charge anymore. We investigate online algorithms for the decision maker to decide when to buy the discount plan and when to cancel it without the knowledge of his/her future expenses, aiming at minimizing the overall cost. The problem is an extension of the classic Bahncard Problem, which is applicable for a wide range of online decision scenarios. We propose a novel deterministic online algorithm which can achieve a closed-form competitive ratio upper bounded by 4. We further propose a randomized online algorithm with a smaller competitive ratio and two variants tailored for average-case inputs and time-varying parameters, respectively. Lastly, we evaluate our algorithms against state-of-the-art online benchmark algorithms in two real-world scenarios.

关键词： online algorithms competitive ratio switching cost minimum commitment

来源：评论

学校读者我要写书评

暂无评论

algorithms for maximum social welfare of online random trading

引用

DISCRETE APPLIED MATHEMATICS 2024年 354卷 229-240页

作者： Chen, Xujin Hu, Xiaodong Wang, Chenhao Wu, Xiaoying Zhang, Mengqi Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Beijing Normal Univ Zhuhai 519087 Peoples R China BNU HKBU United Int Coll Zhuhai 519087 Peoples R China Beijing Inst Astronaut Syst Engn Beijing 100076 Peoples R China

In an online random trading problem, m sellers and n buyers arrive in a random sequential order to meet a decision maker. Each seller possesses an item and each buyer demands an item. All items are identical. Each agent (seller or buyer) has a positive valuation on one item and reveals her valuation to the decision maker when she arrives. The decision maker, who knows only m and n in advance, uses an online algorithm to make an irrevocable decision on whether or not to trade with the arriving agent at her arrival time. We design online algorithms to maximize the social welfare, i.e., the expected total valuation of the agents who possess items on hand at the end of trading process. For the single-buyer trading, our algorithm achieves a tight competitive ratio of 1 + 1 / m . For the single -seller trading, when n tends to infinity, we establish lower bound 3.258 and upper bound 4.189 on the competitive ratio. When both m and n are sufficiently large, our algorithm achieves an asymptotic competitive ratio no more than 1 + O ( m - 1 / 3 ln m ). (c) 2023 Elsevier B.V. All rights reserved.

关键词： online algorithms Competitive ratio Secretary problem Random intermediation

来源：评论

学校读者我要写书评

暂无评论

online Stochastic Matching: New algorithms and Bounds

引用

ALGORITHMICA 2020年第10期82卷 2737-2783页

作者： Brubach, Brian Sankararaman, Karthik Abinav Srinivasan, Aravind Xu, Pan Univ Maryland College Pk MD 20742 USA New Jersey Inst Technol Newark NJ 07102 USA

online matching has received significant attention in recent years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/ ) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam (WINE, 2011) to 0.705;and (b) the vertexweighted case, where we improve the 0.7250 ratio of Jaillet and Lu (Math Oper Res 39(3):624-646, 2013) to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/ . For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/ by proposing a strengthened LP benchmark. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution;however, these give us less control over the structure of . We next remove all these additional constraints and randomly move from to a feasible point on the matching polytope with all coordinates being from the set {0, 1/k, 2/k,., 1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (2013) and is a tractable structure for algorithm design and analysis. The appropriate rand

关键词： online algorithms Randomized algorithms Bipartite matching Internet advertising

来源：评论

学校读者我要写书评

暂无评论

On Conceptually Simple algorithms for Variants of online Bipartite Matching

引用

THEORY OF COMPUTING SYSTEMS 2019年第8期63卷 1781-1818页

作者： Borodin, Allan Pankratov, Denis Salehi-Abari, Amirali Univ Toronto Dept Comp Sci Toronto ON Canada Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada Univ Ontario Inst Technol Fac Business & IT Oshawa ON Canada

We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio in this model is 1/2, which is achieved by any greedy algorithm. Durr et al. (2016) presented a 2-pass algorithm Category-Advice with approximation ratio 3/5. We extend their algorithm to multiple passes. We prove the exact approximation ratio for the k-pass Category-Advice algorithm for all k >= 1, and show that the approximation ratio converges quickly to the inverse of the golden ratio 2/(1+5)approximate to 0.618\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2/(1+\sqrt {5}) \approx 0.618$\end{document} as k goes to infinity. We then consider a natural adaptation of a well-known offline MinGreedy algorithm to the online stochastic IID model, which we call MinDegree. In spite of excellent empirical performance of MinGreedy, it was recently shown to have approximation ratio 1/2 in the adversarial offline setting - the approximation ratio achieved by any greedy algorithm. Our result in the online known IID model is, in spirit, similar to the offline result, but the proof is different. We show that MinDegree cannot achieve an approximation ratio better than 1 - 1/e, which is guaranteed by any consistent greedy algorithm in the known IID model. Finally, following the work in Besser and Poloczek (Algorithmica 2017(1), 201-234, 2017), we depart from an adversarial or stochastic ordering and investigate a natural randomized algorithm (MinRanking) in the priority model. Although the priority model allows the algorithm to choose the input ordering in a general but well defined way, this natural algorithm cannot obtain the approximation of the Ranking algorithm in the ROM model.

关键词： Conceptually simple algorithms online algorithms Priority algorithms Bipartite matching Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED LOWER BOUND FOR online BIN PACKING algorithms

引用

INFORMATION PROCESSING LETTERS 1992年第5期43卷 277-284页

作者： VANVLIET, A ERASMUS UNIV INST TINBERGEN3000 DR ROTTERDAMNETHERLANDS ATTILA JOZSEF UNIV H-6701 SZEGEDHUNGARY

In 1980 Liang proved that every on-line algorithm for the bin packing problem has an asymptotic worst case ratio of at least 1.536.... In this paper we give an improved lower bound of 1.540.... For the parametric case... 详细信息

关键词： BIN PACKING LOWER BOUNDS online algorithms COMBINATORIAL PROBLEMS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：