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

Finding diameter-reducing shortcuts in trees

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 153卷

作者： Bilo, Davide Guala, Luciano Leucci, Stefano Sciarria, Luca Pepe Univ Roma Tor Vergata Dept Enterprise Engn Rome Italy Univ Aquila Dept Informat Engn Comp Sci & Math Laquila Italy

In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices embedded in an unknown metric space. An oracle can report the cost of any edge in constant time, and we want to augment T with k shortcuts to minimize the resulting diameter. When k = 1, O(n log n)-time algorithms exist for paths and trees. We show that o(n(2)) queries cannot provide a better than 10/9-approximation for trees when k >= 3. For any constant epsilon > 0, we design a linear-time (1 + epsilon)-approximation algorithm for paths when k = o(root logn), thus establishing a dichotomy between paths and trees for k >= 3. Our algorithm employs an ad-hoc data structure, which we also use in a linear-time 4approximation algorithm for trees, and to compute the diameter of (possibly non-metric) graphs with n + k - 1 edges in time O (nk log n). (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Tree diameter augmentation Fast diameter computation approximation algorithms Time-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2025年 PP卷 PP页

作者： Li, Na Zhou, Chunyi Gao, Yansong Chen, Hui Zhang, Zhi Kuang, Boyu Fu, Anmin Nanjing Univ Sci & Technol Sch Cyber Sci & Engn Nanjing 210094 Peoples R China Xidian Univ State Key Lab Integrated Serv Networks Xian 710071 Peoples R China Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310058 Peoples R China Univ Western Australia Dept Comp Sci & Software Engn Perth WA 6009 Australia Nanjing Univ Sci & Technol Sch Comp Sci & Engn Nanjing 210094 Peoples R China

Personal digital data is a critical asset, and governments worldwide have enforced laws and regulations to protect data privacy. Data users have been endowed with the "right to be forgotten" (RTBF) of their data. In the course of machine learning (ML), the forgotten right requires a model provider to delete user data and its subsequent impact on ML models upon user requests. Machine unlearning (MU) emerges to address this, which has garnered ever-increasing attention from both industry and academia. Specifically, MU allows model providers to eliminate the influence of unlearned data without retraining the model from scratch, ensuring the model behaves as if it never encountered this data. While the area has developed rapidly, there is a lack of comprehensive surveys to capture the latest advancements. Recognizing this shortage, we conduct an extensive exploration to map the landscape of MU including the (fine-grained) taxonomy of unlearning algorithms under centralized and distributed settings, debate on approximate unlearning, verification and evaluation metrics, and challenges and solutions across various applications. We also focus on the motivations, challenges, and specific methods for deploying unlearning in large language models (LLMs), as well as the potential attacks targeting unlearning processes. The survey concludes by outlining potential directions for future research, hoping to serve as a beacon for interested scholars.

关键词： Data models Surveys Measurement Training Electronic mail Data privacy Taxonomy General Data Protection Regulation Computational modeling approximation algorithms federated learning (FL) large language model (LLM) machine learning (ML) machine unlearning (MU)

来源：评论

学校读者我要写书评

暂无评论

Architecting Path Selection Method for Incremental Evolution in System-of-Systems

引用

IEEE SYSTEMS JOURNAL 2025年

作者： Fang, Zhemei Chen, Dazhi Ju, Qi Wang, Jianbo Huazhong Univ Sci & Technol Sch Artificial Intelligence & Automat Natl Key Lab Sci & Technol Multispectral Informat Wuhan 430074 Peoples R China China Ship Dev & Design Ctr Wuhan 430064 Peoples R China

Architecture design for system-of-systems (SoSs) is a complex challenge due to interdependencies, uncertainties, and the large design space. The evolutionary nature of SoSs necessitates a multistage architecting process, adding further complexity. This article, thus, proposes a deep reinforcement learning based evolutionary architecture path selection method that considers uncertainties and interdependency. The approach employs an architecture framework to guide the design and defines SoS architecture decisions as the addition of systems and the allocation of operational architecture to physical architecture across sequential stages. Capability evaluation leverages a capability-activity-system structure, supported by a functional dependency network analysis method. Utilizing a deep neural network as a functional approximator to predict future SoS capability, the article develops a proximal policy optimization (PPO) algorithm that balances immediate and future needs. Applied to a mosaic warfare-oriented naval antisubmarine SoS, the proposed method outperforms heuristic optimization techniques by achieving higher SoS capability, reduced instability, and fewer violations of budget and intermediate requirements constraints in both deterministic and stochastic scenarios. These results highlight the PPO method's effectiveness in addressing SoS architecting path selection challenges under uncertainty.

关键词： Computer architecture Uncertainty Computational modeling Decision making Architecture Standards Resource management Prediction algorithms Planning approximation algorithms Architecture design capability aggregation incremental evolution reinforcement learning (RL) system-of-systems (SoSs)

来源：评论

学校读者我要写书评

暂无评论

Performance Improvements Through Advanced PV Backtracking on Uneven Terrain

引用

IEEE JOURNAL OF PHOTOVOLTAICS 2025年

作者： Cooper, Emma Anderson, Kevin Riley, Dan Sandia Natl Labs Albuquerque NM 87185 USA

The climatic sensitivity of new terrain-aware backtracking algorithms is evaluated across 800 locations in the continental USA on a representative synthetic rolling terrain. We find that a global optimization approach to backtracking results in climate-specific annual energy gains of 2.4%-3.2% relative to a traditional backtracking algorithm baseline. We identify a strong logarithmic correlation between local diffuse fraction and yield improvement, and highlight the effect of seasonal precipitation on performance gains. We also find that a backtracking approach, which approximates the terrain as constant, does not offer significant annual energy gains over the baseline on the synthetic terrain. Our findings suggest that specific yield from backtracking in the USA can be improved by as much as 88 kWh/kW by considering terrain when selecting a backtracking algorithm.

关键词： Backtracking Target tracking Sun Performance gain Meteorology Photovoltaic systems Geometry approximation algorithms Torque Solar irradiance performance modeling shading single-axis tracking

来源：评论

学校读者我要写书评

暂无评论

A Range-Free Node Localization Method Based on MinMax Error Criterion for Sparse Anchors Wireless Sensor Networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2024年第6期73卷 9182-9186页

作者： Hu, Zhentao Zhou, Lin Zhang, Lu Jin, Yong Wei, Qian Henan Univ Sch Artificial Intelligence Zhengzhou 450046 Peoples R China

Current range-free node localization method experiences low localization accuracy in sparse anchors wireless sensor networks (WSN). To this end, a novel range-free node localization model based on minimize maximum error criterion is proposed in this letter. Moreover, an iterative localization algorithm called MinMax-DV-hop is proposed to tackle the nonconvex and non-differentiable objective function of proposed model too. Specifically, auxiliary variable is introduced to recast the minimum-maximum optimization into one with a linear object function, convex constraints and nonconvex constraints. And then, nonconvex constraints are tightened to linear inequality constraints by using its first-order Taylor expansions, thus a successive convex approximation method can be designed to iteratively solve the optimization problem finally. Simulations show that the MinMax-DV-hop experiences higher localization accuracy in sparse anchors WSN than those of the comparisons algorithm.

关键词： Location awareness Wireless sensor networks Computational modeling Computational complexity approximation algorithms Taylor series Cost function Localization optimization range-free sparse anchors wireless sensor networks (WSN)

来源：评论

学校读者我要写书评

暂无评论

Beampattern Synthesis With Dynamic Range Ratio Constraint via Sequential Convex Optimization

引用

IEEE ANTENNAS AND WIRELESS PROPAGATION LETTERS 2024年第10期23卷 3227-3231页

作者： Li, Lingrui Zhang, Xuejing He, Zishu Univ Elect Sci & Technol China Chengdu 611731 Peoples R China

In this letter, we consider beampattern synthesis with a constraint on the dynamic range ratio (DRR), which is defined as the proportion between the maximum and minimum amplitude excitations applied to the array elements. Utilizing the trigonometric function technique, we reformulate and simplify the nonconvex constraint on DRR. This allows us to derive a new beampattern synthesis formulation with DRR constraint, which can be solved through sequential convex optimization. Compared with existing algorithms, the proposed algorithm can be executed very easily. Moreover, our algorithm exhibits high effectiveness on both focused and shaped beampatterns. Both theoretical and simulation results confirm that the proposed algorithm does not rely on the initial setting and exhibits good convergence performance. Representative simulations are provided to demonstrate the effectiveness and superiority of the proposed algorithm in various scenarios.

关键词： Convex functions Heuristic algorithms approximation algorithms Optimization Dynamic range Convergence Iterative algorithms Beampattern synthesis convex optimization dynamic range ratio (DRR) constraint focused beampattern shaped beampattern

来源：评论

学校读者我要写书评

暂无评论

A Bi-selection Method Based on Consistent Matrix for Large-Scale Datasets

引用

IEEE Transactions on Fuzzy Systems 2025年第6期33卷 1992-2005页

作者： Quan, Jinsheng Qiao, Fengcai Yang, Tian Shen, Shuo Qian, Yuhua Hunan Normal University Hunan Provincial Key Laboratory of Intelligent Computing and Language Information Processing Institute of Interdisciplinary Studies Changsha410081 China National University of Defense Technology College of Advanced Interdisciplinary Studies Changsha410081 China Shanxi University Institute of Big Data Science and Industry Taiyuan030006 China

Biselection (feature and sample selection) enhances the efficiency and accuracy of machine learning models when handling large-scale data. Fuzzy rough sets, an uncertainty mathematics model known for its excellent interpretability, are widely used in machine learning, particularly for feature selection. While the consistent matrix has significantly improved the computational efficiency and scalability of feature selection, like most fuzzy rough set-based methods, it focuses only on feature selection and seldom incorporates sample selection. This feature-centric approach can limit classification performance, particularly in noisy and large-scale datasets where both features and samples require judicious selection. To overcome these limitations, this article explores the integration of sample selection with feature selection. First, we introduce a β-consistent granulation method to generate more accurate and concise fuzzy information granules, reducing the impact of noisy samples. In addition, a novel membership function is employed to distinguish noise while simultaneously evaluating both features and samples. As a result, a biselection algorithm with linear computation complexity is proposed to select high-quality features and samples. Numerical experiments demonstrate that, compared to eleven representative algorithms, our proposed method achieves an average accuracy improvement of 9.66% and a 933-fold increase in efficiency. © 2025 IEEE.

关键词： Rough sets Noise Feature extraction Classification algorithms Accuracy Machine learning Information systems Data models Computational efficiency approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions

A simple polynomial-time approximation algorithm for the tot...

引用

Symposium on Simplicity in algorithms (SOSA)

作者： Feng, Weiming Guo, Heng Jerrum, Mark Wang, Jiaheng Univ Edinburgh Sch Informat Edinburgh Midlothian Scotland Queen Mary Univ London Sch Math Sci London England

We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.

ISBN: (纸本)9781611977585

We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Deterministic Better-than-3/2 approximation Algorithm for Metric TSP 1

引用

24th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Karlin, Anna R. Klein, Nathan Gharan, Shayan Oveis Univ Washington Seattle WA 98195 USA

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic 3/2-epsilon approximation algorithm for metric TSP for some epsilon > 10(-36). To obtain our result, we apply the method of conditional expectation to an objective function constructed in prior work which was used to certify that the expected cost of the algorithm is at most 3/2 - epsilon times the cost of an optimal solution to the subtour elimination LP. The proof in this work involves showing that the expected value of this objective function can be computed in polynomial time (at all stages of the algorithm's execution).

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sorting-Based Soft-Demapping Algorithm for LoRa Systems

引用

IEEE COMMUNICATIONS LETTERS 2024年第7期28卷 1534-1538页

作者： Du, Weimin Li, Dongmin Li, Fan Han, Fei Xian Univ Posts & Telecommun Sch Commun & Informat Engn Xian 710121 Peoples R China Qingdao Topscomm Commun Co Ltd Qingdao 266109 Peoples R China

In low-complexity long-range (LoRa) systems, the prevailing decoding technique is based on hard-decision information due to the computationally intensive nature of the conventional maximum a posteriori probability in log-domain (Max-Log-MAP) soft demapper. In this letter, we propose a sorting-based soft-demapping (SSD) algorithm for LoRa systems. Our proposed algorithm reduces the complexity order of the soft-demapper from O(M log M-2) to O(M), where M=2(SF) and SF represents the spreading factor, thus matching the complexity of hard decision. Importantly, this complexity reduction does not lead to any substantial performance degradation when compared to the Max-Log-MAP demapper. As a result, soft decoding can be employed in low-complexity LoRa systems to effectively enhance receiver sensitivity.

关键词： Complexity theory Symbols Modulation Decoding approximation algorithms Chirp Quadrature amplitude modulation LoRa modulation soft demapper Max-Log-MAP demapper log-likelihood ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：