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

Fast Data-Driven greedy Sensor Selection for Ridge Regression

IEEE SENSORS JOURNAL 2025年第6期25卷 10030-10045页

作者： Sasaki, Yasuo Yamada, Keigo Nagata, Takayuki Saito, Yuji Nonomura, Taku Nagoya Univ Dept Aerosp Engn Nagoya 4648603 Japan Tohoku Univ Dept Aerosp Engn Sendai 9808579 Japan Tohoku Univ Frontier Res Inst Interdisciplinary Sci Sendai 9808578 Japan

We propose a data-driven sensor-selection algorithm for accurate estimation of the target variables from the selected measurements. The target variables are assumed to be estimated by a ridge-regression estimator, which is trained based on the data. The proposed algorithm greedily selects sensors for minimizing the cost function of the estimator. Sensor selection that prevents overfitting of the resulting estimator can be realized by setting a positive regularization parameter. The greedy solution is computed in quite a short time by using some recurrent relations that we derive. The effectiveness of the proposed algorithm is verified for artificial datasets that are generated from linear systems and a real-wold dataset that is aimed for the selection of pressure-sensor locations for estimating the yaw angle of a ground vehicle. The demonstration for the datasets reveals that the proposed algorithm computes a sensor set, resulting in more accurate estimation than existing data-driven selection algorithms in some conditions. Furthermore, it is confirmed that setting a positive regularization parameter in the proposed algorithm leads to accurate estimation when overfitting is problematic.

关键词： Sensors Vectors greedy algorithms Overfitting Accuracy Linear programming Intelligent sensors Computational modeling Training Standards Keywords greedy algorithm ridge regression sensor selection

来源：评论

学校读者我要写书评

暂无评论

Approximation ratio of the min-degree greedy algorithm for Maximum Independent Set on interval and chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2025年 360卷 275-281页

作者： Chaplick, Steven Frohn, Martin Kelk, Steven Lottermoser, Johann Mihalak, Matus Maastricht Univ Dept Adv Comp Sci DACS Maastricht Netherlands

In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a (2/3)-approximation for the MAXIMUM INDEPENDENT SET problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a (1/2)-approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of 3/triangle+2 of the greedy algorithm for general graphs of maximum degree triangle. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： greedy algorithms Maximum independent set Chordal graphs Interval graphs Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy Selection for Heterogeneous Sensors

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2025年 73卷 1394-1409页

作者： Majumder, Kaushani Pillai, Sibi Raj B. Mulleti, Satish Indian Inst Technol Dept Elect Engn Mumbai 400076 India

Simultaneous operation of all sensors in a large-scale sensor network is power-consuming and computationally expensive. Hence, it is desirable to select fewer sensors. A greedy algorithm is widely used for sensor selection in homogeneous networks with a theoretical worst-case performance of ( 1-1/e) approximate to 63% of the optimal performance when optimizing submodular metrics. For heterogeneous sensor networks (HSNs) comprising multiple sets of sensors, most of the existing sensor selection methods optimize the performance constrained by a budget on the total value of the selected sensors. However, in many applications, the number of sensors to select from each set is known apriori and solutions are not well-explored. For this problem, we propose a joint greedy heterogeneous sensor selection algorithm. Theoretically, we show that the worst-case performance of the proposed algorithm is bounded to 50$% of the optimum for submodular cost metrics. In the special case of HSNs with two sensor networks, the performance guarantee can be improved to 63% when the number of sensors to select from one set is much smaller than the other. To validate our results experimentally, we propose a submodular metric based on the frame potential measure that considers both the correlation among the sensor measurements and their heterogeneity. We prove theoretical bounds for the mean squared error of the solution when this performance metric is used. We validate our results through simulation experiments considering both linear and non-linear measurement models corrupted by additive noise and quantization errors. Our experiments show that the proposed algorithm results in 4- 10 dB lower error than existing methods.

关键词： Sensors Sensor phenomena and characterization Costs Measurement Vectors Signal processing algorithms Noise measurement Intelligent sensors greedy algorithms Accuracy Sensor selection heterogeneous sensor networks submodular maximization greedy algorithm frame potential

来源：评论

学校读者我要写书评

暂无评论

m-BRe: New Variants for the Backward Replacement Approach to Enhance the Compression Capabilities of the Forward greedy Pursuit

引用

IEEE ACCESS 2024年 12卷 138646-138662页

作者： Omara, A. N. Alotaibi, Abdullah Shawan Elect Res Inst Comp & Syst Dept Cairo 4473221 Egypt Shaqra Univ Comp Sci Dept Shaqra 11911 Saudi Arabia Ahram Canadian Univ Fac Comp Sci & Informat Technol Giza 3221405 Egypt

This paper introduces two variants of the backward replacement approach, T-BRe and H-BRe, aimed at enhancing the compression capabilities of forward greedy pursuit algorithms. The effectiveness of these methods is evaluated using three greedy pursuit algorithms (OMP, OOMP, and FBP) through simulations conducted on image and speech datasets with a mathematically generated dictionary. Additionally, a mathematical analysis of the H-BRe algorithm is provided to validate its effectiveness and address inherent limitations. Both analysis and simulations confirm that the H-BRe algorithm significantly improves the compression capabilities of forward greedy pursuit algorithms. The degree of enhancement varies depending on factors such as the forward modeling technique, stopping criterion, and the stochastic nature of the backward replacements. The high-performance (H) variants demonstrate superior performance across various modeling approaches, as evidenced by metrics such as PESQ and SSIM values, while the B and T variants also exhibit efficiency in specific scenarios. Despite these promising results, our methods encounter limitations such as time complexity, local error minimization, dependence on atom types, and the assumption of linear distribution. Future research directions include optimizing time complexity, balancing compression-quality trade-offs, globally minimizing replacement errors, exploring diverse atom types, and refining mathematical assumptions to further elucidate H-BRe's performance characteristics.

关键词： Matching pursuit algorithms Vectors Symmetric matrices Indexes Data compression Sparse matrices Signal processing algorithms greedy algorithms Backward elimination backward replacement data compression forward greedy pursuit 2D and cubic distortion matrix sparse coding

来源：评论

学校读者我要写书评

暂无评论

Adaptive meshfree approximation for linear elliptic partial differential equations with PDE-greedy kernel methods

引用

BIT NUMERICAL MATHEMATICS 2025年第1期65卷 1-36页

作者： Wenzel, Tizian Winkle, Daniel Santin, Gabriele Haasdonk, Bernard Ludwig Maximilians Univ Munchen Dept Math Munich Germany Univ Stuttgart Inst Stochast & Applicat Stuttgart Germany Ca Foscari Univ Venice Venice Italy Univ Stuttgart Inst Appl Anal & Numer Simulat Stuttgart Germany

We consider meshless approximation for solutions of boundary value problems (BVPs) of elliptic Partial Differential Equations (PDEs) via symmetric kernel collocation. We discuss the importance of the choice of the collocation points, in particular by using greedy kernel methods. We introduce a scale of PDE-greedy selection criteria that generalizes existing techniques, such as the PDE-P-greedy and the PDE-f-greedy rules for collocation point selection. For these greedy selection criteria we provide bounds on the approximation error in terms of the number of greedily selected points and analyze the corresponding convergence rates. This is achieved by a novel analysis of Kolmogorov widths of special sets of BVP point-evaluation functionals. Especially, we prove that target-data dependent algorithms that make use of the right hand side functions of the BVP exhibit faster convergence rates than the target-data independent PDE-P-greedy. The convergence rate of the PDE-f-greedy possesses a dimension independent rate, which makes it amenable to mitigate the curse of dimensionality. The advantages of these greedy algorithms are highlighted by numerical examples.

关键词： Kernel collocation greedy algorithms Meshfree approximation

来源：评论

学校读者我要写书评

暂无评论

A succinct and approximate greedy algorithm for the Minimum Set Cover Problem

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2024年 81卷

作者： Delgado, Jorge Ferrada, Hector Navarro, Cristobal A. Univ Austral Chile Inst Informat Valdivia Chile

The Minimum Set Cover Problem (MSCP) is a combinatorial optimization problem belonging to the NP- Hard class in computer science. For this reason, there is no algorithm that in the worst case ensures finding an optimal solution in polynomial-time. For a given universe X , the popular greedy heuristic, called greedy-SetCover, is the main theoretical contribution to obtain an approximate solution for the MSCP in polynomial-time, offering an optimal approximate ratio of (ln |X| + 1) . In this article, we propose an approximate algorithm for MSCP within a succinct representation of the input dataset, whose empirical performance improves greedy-SetCover both in quality and execution time, while offering the same optimal approximation ratio for the problem. Our experiments show that the proposed algorithm is magnitudes of times faster than the aforementioned greedy one, obtaining on average a cardinality much closer to the optimal solution. Furthermore, because we work on a succinct representation that allows us to compute operations between sets using bitwise operators, we can process much larger datasets than state-of-the-art solutions. As a result, our proposal is also a suitable alternative for processing large datasets as required by the current Big Data era.

关键词： Combinatorial optimization Set cover NP-Hard greedy algorithms Approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy sets and greedy numerical semigroups

引用

COMMUNICATIONS IN ALGEBRA 2025年第6期53卷 2442-2455页

作者： Perez-Roses, Hebert Serradilla-Merinero, Jose Miguel Bras-Amoros, Maria Univ Rovira & Virgili Dept Comp Sci & Math Avda Paisos Catalans 26 Catalonia 43007 Spain

Motivated by the change-making problem, we extend the notion of greediness to sets of positive integers not containing the element 1, and from there to numerical semigroups. We provide an algorithm to determine if a given set (not necessarily containing the number 1) is greedy. We also give specific conditions for sets of cardinality three, and we prove that numerical semigroups generated by three consecutive integers are greedy.

关键词： Change-making problem greedy algorithms numerical semigroups

来源：评论

学校读者我要写书评

暂无评论

Ultimate greedy Approximation of Independent Sets in Subcubic Graphs

引用

ALGORITHMICA 2024年第11期86卷 3518-3578页

作者： Krysta, Piotr Mari, Mathieu Zhi, Nan Augusta Univ Augusta GA USA Univ Montpellier LIRMM CNRS Montpellier France Univ Liverpool Liverpool England

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization problems. It is known for its inherent hardness of approximation. We focus on the well known minimum-degree greedy algorithm for this problem. This algorithm iteratively chooses a minimum degree vertex in the graph, adds it to the solution and removes its neighbors, until the remaining graph is empty. The approximation ratios of this algorithm have been widely studied, where it is augmented with an advice that tells the greedy algorithm which minimum degree vertex to choose if it is not unique. Our main contribution is a new mathematical theory for the design of such greedy algorithms for MIS with efficiently computable advice and for the analysis of their approximation ratios. Using this theory we obtain the ultimate approximation ratio of 5/4 for greedy algorithms on graphs with maximum degree 3, which completely solves an open problem from the paper by Halld & oacute;rsson and Yoshihara (in: Staples, Eades, Katoh, Moffat (eds) algorithms and computations-ISAAC '95, in 2026 LNCS, Springer, Berlin, Heidelberg, 1995) . Our algorithm is the fastest currently known algorithm for MIS with this approximation ratio on such graphs. We also obtain a simple and short proof of the (Delta+2)/3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\Delta +2)/3$$\end{document}-approximation ratio of any greedy algorithms on graphs with maximum degree Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document}, the result proved previous

关键词： Approximation algorithms greedy algorithms Independent set problem Bounded degree graphs

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of greedy and Auction-Based Resource Allocation algorithms in Ubiquitous Computing Environments

Performance Analysis of Greedy and Auction-Based Resource Al...

引用

IFIP International Conference on Very Large Scale Integration (VLSI-SoC)

作者： Akshay Nagpal Vivekananda Jayaram Manjunatha Sughaturu Krishnappa Nikhil Jagdish Bangad Darshan Mohan Bidkar Manoj Jayantilal Kathiriya Seema G Aarella New Jersey New Jersey USA Texas Texas USA Oracle America Inc California USA Gartner Inc Connecticut USA University of North Texas Texas USA

ISBN: (数字)9798331539672

ISBN: (纸本)9798331539689

In the era of ubiquitous computing, efficient resource allocation is critical to managing the diverse and dynamic environments created by interconnected devices. This paper presents a comprehensive comparative analysis of greedy and auction-based resource allocation algorithms within ubiquitous computing systems. The study examines the performance of these algorithms under three implementation approaches: centralized, decentralized, and hierarchical. We use a process-based discrete-event simulation model to evaluate the algorithms based on key performance metrics, including throughput, average response time, and energy utilization. Our results demonstrate that auction-based algorithms, particularly in a hierarchical implementation, consistently outperform greedy algorithms in both throughput and energy efficiency while maintaining competitive response times. The findings highlight the advantages of auction-based strategies in dynamically adapting to changing conditions and optimizing resource use in complex, decentralized environments. This research contributes valuable insights into optimal resource management strategies for ubiquitous computing, guiding system designers and researchers toward more efficient and scalable solutions. Future work should address the limitations of simplified network and energy models to enhance the applicability of these findings in real-world scenarios.

关键词： greedy algorithms Analytical models Computational modeling Heuristic algorithms Very large scale integration Ubiquitous computing Throughput Energy efficiency Resource management Time factors

来源：评论

学校读者我要写书评

暂无评论

Solving Stochastic Online Food Delivery Problem via Iterated greedy Algorithm With Decomposition-Based Strategy

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2023年第2期53卷 957-969页

作者： Zheng, Jie Wang, Ling Wang, Li Wang, Shengyao Chen, Jing-Fang Wang, Xing Tsinghua Univ Dept Automat Beijing 100084 Peoples R China Meituan Dept Delivery Technol Beijing 100102 Peoples R China

Online food delivery (OFD) service has developed rapidly due to its great convenience for customers, the enormous markets for restaurants and the abundant job openings for riders. However, OFD platforms are encountering enormous challenges, such as massive demand, inevitable uncertainty and short delivery time. This article addresses an OFD problem with stochastic food preparation time. It is a complex NP-hard problem with uncertainty, large search space, strongly coupled subproblems, and high timeliness requirements. To solve the problem, we design an iterated greedy algorithm with a decomposition-based strategy. Concretely speaking, to cope with the large search space due to massive demands, a filtration mechanism is designed by preliminarily selecting suitable riders. To reduce the risk affected by the uncertainty, we introduce a risk-measuring criterion into the objective function and employ a scenario-sampling method. For timeliness requirements caused by short delivery time, we design two time-saving strategies via mathematical analysis, i.e., an adaptive selection mechanism to choose the method with less computational effort and a fast evaluation mechanism based on the small-scale sampling and machine learning model to speed up evaluation. We also prove an upper bound of the stochastic time cost under risk measurement as one of the baseline features to improve the prediction accuracy. The experiments on real-world data sets demonstrate the effectiveness of the proposed algorithm.

关键词： Stochastic processes Uncertainty Costs greedy algorithms Computational modeling Search problems Prediction algorithms Decomposition-based strategy fast evaluation mechanism iterated greedy algorithm machine learning model stochastic online food delivery problem (SOFDP)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：