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

approximation Non-list Scheduling algorithms for Multiprocessor System 1

21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022

作者： Grigoreva, Natalia St. Petersburg State University St. Petersburg Russia

ISBN: (数字)9783031162244

ISBN: (纸本)9783031162237

The multiprocessor scheduling problem is defined as follows: jobs have to be executed on several parallel identical processors. Each job has a positive processing time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. We study the case where precedence constrains exist between jobs and preemption on processors is not allowed. The objective is to minimize the time, by which all jobs are done. The problem is NP-hard in the strong sense. The best-known approximation algorithm is the critical path algorithm, which generates the list no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule, in which a processor is kept idle at a time when it could begin processing a job. The paper proposes a 2-1/m approximation inserted idle time algorithm for the multiprocessor scheduling. To illustrate the efficiency of our approach, we compared two algorithms on randomly generated sets of jobs. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed fractional local ratio and independent set approximation

引用

INFORMATION AND COMPUTATION 2025年 303卷

作者： Halldorsson, Magnus M. Rawitz, Dror Reykjavik Univ Dept Comp Sci Reykjavik Iceland Bar Ilan Univ Fac Engn Ramat Gan Israel

We consider the MAXIMUM WEIGHT INDEPENDENT SET problem, with a focus on obtaining good approximations for graphs of small maximum degree A. We give deterministic local algorithms running in time poly(A, log n ) that come close to matching the best centralized results known and improve the previous distributed approximations by a factor of about 2. More precisely, we obtain approximations below Delta+1/2/2, and a further improvement to 8/5 + s when A = 3. Technically, this is achieved by leveraging the fractional local ratio technique, for a first application in a distributed setting. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： approximation algorithms Distributed algorithms Fractional local ratio Maximum weight independent set

来源：评论

学校读者我要写书评

暂无评论

Data-Driven Modeling of Weakly Nonlinear Circuits via Generalized Transfer Function approximation

引用

IEEE ACCESS 2025年 13卷 2746-2762页

作者： Carlucci, Antonio Gosea, Ion Victor Grivet-Talocia, Stefano Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy Max Planck Inst Dynam Complex Tech Syst CSC Grp D-39106 Magdeburg Germany

This paper presents an extension of the Vector Fitting algorithm with the purpose of constructing compact behavioral models of weakly nonlinear circuits starting from frequency-domain input-output data. Using the concept of generalized transfer function provided by Volterra series theory for nonlinear systems, the algorithm approximates a given dataset of generalized transfer function samples with a black-box multivariate rational model. The fitted model can then be recast into a bilinear state-space form for time-domain analysis. Practical extraction of the required data samples can be carried out by measurement or harmonic balance analysis available in commercial solvers. Examples demonstrating the accuracy and efficiency of the behavioral models include a Low-Dropout Regulator and a Low Noise Amplifier.

关键词： Mathematical models Integrated circuit modeling Numerical models Transfer functions Nonlinear systems Data models Kernel Analytical models Time-domain analysis approximation algorithms Behavioral model nonlinear system vector fitting Volterra series data-driven model non-intrusive model reduction generalized transfer function

来源：评论

学校读者我要写书评

暂无评论

A Simple Finite-Time Analysis of TD Learning With Linear Function approximation

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2025年第2期70卷 1388-1394页

作者： Mitra, Aritra North Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

We study the finite-time convergence of temporal- difference (TD) learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: Is it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm? Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size alpha , the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of O ( alpha(2) ) that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and conclude by providing some examples of such applications.

关键词： Temporal difference learning approximation algorithms Standards Function approximation Convergence Perturbation methods Noise Vectors Heuristic algorithms Delays Finite-time analysis reinforcement learning stochastic approximation temporal difference learning

来源：评论

学校读者我要写书评

暂无评论

Online Learning Under a Separable Stochastic approximation Framework

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2025年第2期47卷 1317-1330页

作者： Gan, Min Su, Xiang-xiang Chen, Guang-yong Chen, Jing Chen, C. L. Philip Qingdao Univ Inst Future Qingdao 266071 Peoples R China Coll Comp Sci & Technol Qingdao 266071 Peoples R China Fuzhou Univ Coll Comp & Data Sci Fuzhou 350108 Peoples R China Univ Fujian Fujian Key Lab Network Comp & Intelligent Informat Key Lab Intelligent Metro Fuzhou 350007 Peoples R China Minist Educ Engn Res Ctr Big Data Intelligence Beijing 100101 Peoples R China Jiangnan Univ Sch Sci Wuxi 214122 Peoples R China Qingdao Univ Coll Comp Sci & Technol Qingdao 266071 Peoples R China South China Univ Technol Sch Comp Sci & Engn Guangzhou 510641 Peoples R China

We propose an online learning algorithm tailored for a class of machine learning models within a separable stochastic approximation framework. The central idea of our approach is to exploit the inherent separability in many models, recognizing that certain parameters are easier to optimize than others. This paper focuses on models where some parameters exhibit linear characteristics, which are common in machine learning applications. In our proposed algorithm, the linear parameters are updated using the recursive least squares (RLS) algorithm, akin to a stochastic Newton method. Subsequently, based on these updated linear parameters, the nonlinear parameters are adjusted using the stochastic gradient method (SGD). This dual-update mechanism can be viewed as a stochastic approximation variant of block coordinate gradient descent, where one subset of parameters is optimized using a second-order method while the other is handled with a first-order approach. We establish the global convergence of our online algorithm for non-convex cases in terms of the expected violation of first-order optimality conditions. Numerical experiments demonstrate that our method achieves significantly faster initial convergence and produces more robust performance compared to other popular learning algorithms. Additionally, our algorithm exhibits reduced sensitivity to learning rates and outperforms the recently proposed slimTrain algorithm (Newman et al. 2022). For validation, the code has been made available on GitHub.

关键词： Stochastic processes approximation algorithms Optimization Machine learning algorithms Machine learning Convergence Artificial neural networks Training Minimization Convex functions Online learning recursive least squares stochastic approximation variable projection

来源：评论

学校读者我要写书评

暂无评论

Deciding Truck Platooning Operational Rules With Stochastic approximation for Vehicle Safe Overtaking on Two-Lane Undivided Highways

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2025年第5期26卷 6201-6215页

作者： Song, Yu Univ Wyoming Dept Civil & Architectural Engn & Construct Manage Laramie WY 82071 USA

Truck platooning is a promising technology to improve freight transport efficiency. However, this technology has primarily been explored on multi-lane divided highways, neglecting potential applications on two-lane undivided highways prevalent in rural areas. This paper addresses the challenges of deploying truck platooning on such highways, focusing on overtaking safety. We formulate safe overtaking via stochastic approximation as a feasibility problem. An algorithm is proposed to determine operational rules for truck platooning, considering factors including traffic flow, road segment geometry, and vehicle dynamics. Values for truck platooning operational parameters such as speed, inter-truck following gap, and number of trucks in platoon are decided which ensure overall overtaking safety. The algorithm is iterative and depends on first order information, avoiding possible complex computations of stochastic objective with respect to truck platooning operational parameters. The algorithm is general and adapts to different roadway and traffic conditions and weights on platooning parameters. We show that computation of the algorithm is linear in sample size used in approximation. Simulations show that the algorithm-generated platooning rules offer an overtaking safety guarantee of up to 93% on a straight and flat road segment with sparse traffic.

关键词： Safety Roads Trajectory Geometry approximation algorithms Regulation Estimation Vehicles Vectors Sensors Connected and automated vehicle trucking road geometry passing sight distance road safety traffic regulations

来源：评论

学校读者我要写书评

暂无评论

MBS: A High-Precision approximation Method for Softmax and Efficient Hardware Implementation

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2025年

作者： Wu, Yuanchen Xie, Zhiheng Pan, Hongbing Wang, Yuxuan Nanjing Univ Sch Elect Sci & Engn Nanjing 210023 Peoples R China

The softmax function needs to be frequently used in the multi-head attention layer of Transformer networks. Compared to DNNs and other networks, Transformers have higher computational complexity, requiring higher accuracy and hardware performance for softmax function calculations. Therefore, we propose mixed-base softmax (MBS) for the first time for the approximation of the softmax function. This method combines exponential functions with bases of 2 and 4, which is advantageous for hardware implementation. MBS has a high similarity to the softmax function and demonstrates advanced performance during inference in Transformer network. Through algorithm transformation and hardware optimization, we have designed a low-complexity and highly parallel hardware architecture, which only occupies few additional hardware resources compared to base-2 softmax but achieves higher accuracy. Experimental results show that, under TSMC 90nm CMOS technology at the frequency of 0.5 GHz, our design can achieve the efficiency of 236.18 Gps/(mm(2)& sdot;mW) with the area of 4234 mu m(2). Furthermore, MBS exhibits higher computational accuracy and inference precision compared with base-2 softmax.

关键词： Hardware Accuracy Transformers Computational modeling Computer architecture approximation methods approximation algorithms Linear approximation Inference algorithms Frequency modulation Softmax function mixed-base softmax transformer neural network high-efficiency hardware

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for age of information minimization in UAV grid patrols

引用

AD HOC NETWORKS 2025年 166卷

作者： Wang, Weiqi Xu, Jin Univ Victoria Dept Phys & Astron 3800 Finnerty Rd Victoria BC V8P 5C2 Canada Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China

Motivated by the critical need for unmanned aerial vehicles (UAVs) to patrol grid systems in hazardous and dynamically changing environments, this study addresses a routing problem aimed at minimizing the time- average Age of Information (AoI) for edges in general graphs. We establish a lower bound for all feasible patrol policies and demonstrate that this bound is tight when the graph contains an Eulerian cycle. For graphs without Eulerian cycles, it becomes challenging to identify the optimal patrol strategy due to the extensive range of feasible options. Our analysis shows that restricting the strategy to periodic sequences still results in an exponentially large number of possible strategies. To address this complexity, we introduce two polynomial-time approximation schemes, each involving a two-step process: constructing multigraphs first and then embedding Eulerian cycles within these multigraphs. We prove that both schemes achieve an approximation ratio of 2. Further, both analytical and numerical results suggest that evenly and sparsely distributing edge visits within a periodic route significantly reduces the average AoI compared to strategies that merely minimize the route travel distance. Building on this insight, we propose a heuristic method that not only maintains the approximation ratio of 2 but also ensures robust performance across varying random graphs.

关键词： UAV grid patrols Age of information approximation algorithms approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Improving Accuracy of Interpolation Algorithm in EMT Simulation: A Padé approximation and Switching Theorem Based Approach

引用

IEEE TRANSACTIONS ON INDUSTRY APPLICATIONS 2025年第1期61卷 1148-1160页

作者： Cao, Yang Gu, Wei Xu, Mingwang Zhang, Fei Chen, Shuaixian Liu, Wei Southeast Univ Sch Elect Engn Nanjing 210096 Jiangsu Peoples R China Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Jiangsu Peoples R China

As renewable sources and power electronic devices become more prevalent in the power system, the characteristics of power system are now shaped by power electronics, which presents new challenges for the acceleration algorithm used in electromagnetic transient (EMT) simulation. In this context, this paper refines five key technical points of interpolation algorithms and proposes an improved interpolation algorithm. In particular, the Pade approximation is adopted and combined with numerical integration methods to establish a discrete model for accuracy and stability improvement. The switching theorem is used for re-initialization, which further reduces the switching error and reflects more realistic switching transients. Moreover, the algorithm's stability is theoretically proved through Lyapunov stability analysis. With the improved interpolation algorithm, switching transients can be accurately simulated while maintaining high simulation efficiency and stability. The performance of the proposed method is validated by both simulation and experimental tests.

关键词： Switches Interpolation Accuracy Power system stability approximation algorithms Numerical stability Transient analysis Power electronics Oscillators Stability criteria EMT simulation power electronics interpolation pad & eacute approximation switching theorem stability Lyapunov function

来源：评论

学校读者我要写书评

暂无评论

Shapley Value approximation Based on Complementary Contribution

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第12期36卷 9263-9281页

作者： Sun, Qiheng Zhang, Jiayao Liu, Jinfei Xiong, Li Pei, Jian Ren, Kui Zhejiang Univ Hangzhou 310027 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310027 Zhejiang Peoples R China Emory Univ Comp Sci & Biomed Informat Atlanta GA 30322 USA Duke Univ Trinity Coll Arts & Sci Dept Comp Sci Durham NC 27708 USA

Shapley value provides a unique way to fairly assess each player's contribution in a coalition and has enjoyed many applications. However, the exact computation of Shapley value is #P-hard due to the combinatoric nature of Shapley value. Many existing applications of Shapley value are based on Monte-Carlo approximation, which requires a large number of samples and the assessment of utility on many coalitions to reach high-quality approximation, and thus is still far from being efficient. Can we achieve an efficient approximation of Shapley value by smartly obtaining samples? In this paper, we treat the sampling approach to Shapley value approximation as a stratified sampling problem. Our main technical contributions are a novel stratification design and a sampling method based on Neyman allocation. Moreover, computing the Shapley value in a dynamic setting, where new players may join the game and others may leave it poses an additional challenge due to the considerable cost of recomputing from scratch. To tackle this issue, we propose to capture changes in Shapley value, making our approaches applicable to scenarios with dynamic players. Experimental results on several real data sets and synthetic data sets demonstrate the effectiveness and efficiency of our approaches.

关键词： Resource management Heuristic algorithms Games Data models approximation algorithms Estimation Pricing Approximate algorithms dynamic datasets shapley value

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：