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

Sparse Approximation and Recovery by greedy algorithms

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第7期60卷 3989-4000页

作者： Livshitz, Eugene D. Temlyakov, Vladimir N. Evernote Corp Moscow 121087 Russia Moscow MV Lomonosov State Univ Moscow 121087 Russia Univ S Carolina Columbia SC 29208 USA Steklov Inst Math Moscow 119991 Russia

We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random K-sparse signals within [K(1+ epsilon)] iterations of the orthogonal matching pursuit (OMP). This result shows that in a probabilistic sense, the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the weak Chebyshev greedy algorithm, a generalization of the weak orthogonal matching pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space, our results add some new elements to known results on the Lebesgue-type inequalities for the restricted isometry property dictionaries. Our technique is a development of the recent technique created by Zhang.

关键词： greedy algorithms orthogonal matching pursuit sparse approximation Lebesgue-type inequality probability

来源：评论

学校读者我要写书评

暂无评论

Fast greedy Subset Selection From Large Candidate Solution Sets in Evolutionary Multiobjective Optimization

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2022年第4期26卷 750-764页

作者： Chen, Weiyu Ishibuchi, Hisao Shang, Ke Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China

Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators.

关键词： Optimization greedy algorithms Statistics Sociology Approximation algorithms Evolutionary computation Clustering algorithms Evolutionary many-objective optimization evolutionary multiobjective optimization (EMO) performance indicators submodularity subset selection

来源：评论

学校读者我要写书评

暂无评论

A greedy Algorithm for Optimizing Offshore Wind Transmission Topologies

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2022年第3期37卷 2113-2121页

作者： Hardy, Stephen Ergun, Hakan Van Hertem, Dirk Katholieke Univ Leuven Dept Elect Engn ELECTA B-3000 Leuven Belgium EnergyVille Genk Belgium

This work develops a mathematical formulation to determine the combinatorial search space of the Offshore Wind Transmission Optimization Problem (OWTOP). The model accounts for Capital Expenditures (CAPEX), Corrective Maintenance (CM), losses and Expected Energy Not Transmitted (EENT) and determines the optimal radial transmission system topology to connect a number of Offshore Wind Power Plants (OWPPs) to the shore. The model also considers the stochastic nature of wind. In this context a greedy search algorithm is developed capable of finding the globally optimal solution for the location of offshore substations (OSSs), sizing of the transmission infrastructure and topological layout. Rather than a single optimal solution, the algorithm finds a solution space of feasible topologies, bounded from below by the optimal radial solution. The algorithm is applied to 4 test cases including one based on the Belgian North Sea area. It is shown to outperform a traditional Transmission Network Expansion Problem (TNEP) formulation both in computational speed and solution quality.

关键词： Topology Transformers Costs Network topology Optimization Capacity planning Power cables Wind energy offshore installations optimization greedy algorithms circuit topology power transmission

来源：评论

学校读者我要写书评

暂无评论

Efficient Intervention in the Spread of Misinformation in Social Networks

引用

IEEE ACCESS 2024年 12卷 133489-133498页

作者： Sakiyama, Takumi Nakajima, Kazuki Aida, Masaki Tokyo Metropolitan Univ Grad Sch Syst Design Tokyo 1910065 Japan

The spread of misinformation through social media has often impacted public opinion and precipitated social disruption. In response to such real-world instances, strategies to intervene in the diffusion of misinformation among individuals have been developed. A basic intervention approach involves disseminating correct information to the largest possible population in a social network. In the present study, we investigate the problem of identifying a set of seed individuals that maximize the spread of correct information throughout a social network where the diffusion of misinformation has occurred. We find that a greedy algorithm for this problem lacks theoretical guarantees regarding the approximation ratio of the spread of correct information and requires considerable computation time in large-scale networks. To address this efficiency issue, we propose a heuristic algorithm called MCEaSyIM. The proposed algorithm exploits stochastic properties of the simultaneous diffusion of misinformation and correct information on the network to efficiently compute the seed individuals that approximately maximize the expected diffusion of correct information. Our algorithm achieves a comparable spread of correct information in a considerably faster computation time compared with the greedy algorithm. In addition, our algorithm achieves a broader spread of correct information in a reasonable computation time than topology-based heuristics, such as the method that selects seed individuals with the largest out-neighbors that have not been activated with misinformation. Moreover, we found that the effectiveness of our algorithm in spreading correct information is partially associated with the degree assortativity of the network. We expect that our algorithm will serve as an efficient and effective intervention strategy in combating the spread of misinformation in social networks.

关键词： Fake news Social networking (online) greedy algorithms Integrated circuit modeling Heuristic algorithms Diffusion models Approximation algorithms influence maximization misinformation online social networks

来源：评论

学校读者我要写书评

暂无评论

Assessment of Sensor Optimization Methods Toward State Estimation in a High-Dimensional System Using Kalman Filter

引用

IEEE SENSORS JOURNAL 2024年第11期24卷 18012-18023页

作者： Nagata, Takayuki Sasaki, Yasuo Yamada, Keigo Watanabe, Masahito Tsubakino, Daisuke Nonomura, Taku Nagoya Univ Dept Aerosp Engn Nagoya Aichi 4648603 Japan Tohoku Univ Dept Aerosp Engn Sendai Miyagi 9808579 Japan

The characteristics of the sensor selection method based on various algorithms for state estimation in a high-dimensional system using the Kalman filter were investigated. Sensors were selected based on the error covariance matrix of the Kalman filter. The performance of the sensor selection methods based on different algorithms, semidefinite programming (SDP), approximate convex relaxation, and greedy algorithm, including newly formulated methods, were compared by varying the number of potential sensor locations and the number of sensors to be selected under several noise ratio conditions. Two sensor selection methods for state estimation in a high-dimensional system using a Kalman filter were newly proposed based on the SDP with gain formulation and approximate convex relaxation, and the characteristics of the method including the previously proposed method were compared in a high-dimensional system. Although the condition was limited at n < O(10(3)), the approximate convex relaxation method and its randomized method are effective in terms of computational time and objective value for a small-scale problem. The objective value obtained by the greedy method shows the best performance compared to the other methods in almost all investigated conditions. Particularly, the greedy method outperforms other methods when the number of selected sensors is small. In addition, only the greedy method can handle the large-scale problem of n>O(10(4)). Overall, the greedy-based method is found to be favorable in large-scale problems in terms of computation time and the performance of the obtained sensor set.

关键词： Sensor phenomena and characterization Kalman filters Sensor systems Covariance matrices Optimization Vectors greedy algorithms Kalman filter optimal design of experiment sensor selection

来源：评论

学校读者我要写书评

暂无评论

Influence Nodes Identifying Method via Community-Based Backward Generating Network Framework

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第1期11卷 236-253页

作者： Liu, Xiaoyang Ye, Shu Fiumara, Giacomo De Meo, Pasquale Chongqing Univ Technol Sch Comp Sci & Engn Chongqing 400054 Peoples R China Univ Messina MIFT Dept I-98166 Messina Italy Univ Messina Dept Ancient & Modern Civilizat I-98166 Messina Italy

Traditional methods for influential node identification usually require time consuming network traversal to select the candidate node set. In this article we propose a new influence nodes identification method, called Community-based Backward Generating Network (CBGN). First, the influence maximization framework is built by integrating community detection and Backward Generation Network (BGN);then, nodes in each community are selected using a new method, called imp_BGN, that uses graph traversal to assist the construction of BGN. The ultimate goal of the network generation method is to find a sequence of nodes that can minimize the cost function, and to select high influential nodes without restoring the original network during network construction. finally, an improved submodular CELF (Cost Effective Lazy Forward) algorithm is proposed to hunt for the final seed node from the candidate node pool considering the location relation and structural similarity among nodes. Experimental results show that: in the SIR (susceptible-infected-recovered) model experiment, compared with the benchmark methods, the infection scale of the proposed CBGN method in 6 real networks is improved by 0.45%, 0.59%, 0.84%, 1.05%, 0.71% and 0.14%, respectively.

关键词： Robustness Heuristic algorithms greedy algorithms Clustering algorithms Monte Carlo methods Indexes Diffusion processes Node identify influence maximization community detection backward generation network

来源：评论

学校读者我要写书评

暂无评论

A Graph Machine Learning Framework to Compute Zero Forcing Sets in Graphs

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第2期11卷 2110-2123页

作者： Ahmad, Obaid Ullah Shabbir, Mudassir Abbas, Waseem Koutsoukos, Xenofon Univ Texas Dallas Elect Engn Dept Richardson TX 75080 USA Univ Texas Dallas Syst Engn Dept Richardson TX 75080 USA Vanderbilt Univ Comp Sci Dept Nashville TN 37235 USA

This article studies the problem of computing zero-forcing sets (ZFS) in graphs and provides a machine-learning solution. Zero-forcing is a vertex coloring process to color the entire vertex set from a small subset of initially colored vertices constituting a ZFS. Such sets have several applications in network science and networked control systems. However, computing a minimum ZFS is an NP-hard problem, and popular heuristics encounter scalability issues. We investigate the greedy heuristic for this problem and propose a combination of the random selection and greedy algorithm called the random-greedy algorithm, which offers an efficient solution to the ZFS problem. Moreover, we enhance this approach by incorporating a data-driven solution based on graph convolutional networks (GCNs), leveraging a random selection process. Our machine-learning architecture, designed to imitate the greedy algorithm, achieves significant speed improvements, surpassing the computational efficiency of the greedy algorithm by several orders of magnitude. We perform thorough numerical evaluations to demonstrate that the proposed approach is considerably efficient, scalable to graphs about ten times larger than those used in training, and generalizable to several different families of synthetic and real-world graphs with comparable and sometimes better results in terms of the size of ZFS. We also curate a comprehensive database comprising synthetic and real-world graph datasets, including approximate and optimal ZFS solutions. This database serves as a benchmark for training machine-learning models and provides valuable resources for further research and evaluation in this problem domain. Our findings showcase the effectiveness of the proposed machine-learning solution and advance the state-of-the-art in solving the ZFS problem.

关键词： Machine learning greedy algorithms Training Optimization Computer architecture Controllability Scalability Zero-forcing Set graph convolutional network network controllability leader selection problem

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms as locally stratified logic programs 22

Greedy algorithms as locally stratified logic programs

引用

22nd Italian Symposium on Advanced Database Systems, SEBD 2014

作者： Zaniolo, Carlo University of California Los Angeles United States

ISBN: (纸本)9781634391450

The problem of expressing and supporting classical greedy algorithms in Datalog has been the focus of significant research efforts that have produced very interesting specific solutions. But we still lack general treatments that characterize the relation of greedy algorithms to non-monotonic theories and lead to asymptotically optimal implementations. In this paper, we propose a very general solution that begins by identifying a class of locally stratified programs that is a perfect match for greedy algorithms, and leads to simple implementations that achieve optimal asymptotic complexities for well-know greedy algorithms.

关键词： Aggregates Datalog greedy algorithms Horn clauses

来源：评论

学校读者我要写书评

暂无评论

Nondominated-Solution-Based Multi-Objective greedy Sensor Selection for Optimal Design of Experiments

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2022年 70卷 5694-5707页

作者： Nakai, Kumi Sasaki, Yasuo Nagata, Takayuki Yamada, Keigo Saito, Yuji Nonomura, Taku Natl Inst Adv Ind Sci & Technol Tsukuba 3058564 Japan Tohoku Univ Sendai 9808579 Japan Tohoku Univ Japan Soc Promot Sci Sendai 9808579 Japan Tohoku Univ Dept Aerosp Engn Sendai 9808579 Japan

In this study, a nondominated-solution-based multi-objective greedy method is proposed and applied to a sensor selection problem based on the multiple indices of the optimal design of experiments. The proposed method simultaneously considers multiple set functions and applies the idea of Pareto ranking for the selection of sets. Specifically, a new index is iteratively added to the nondominated solutions of sets, and the multi-objective functions are evaluated for new sets. The nondominated solutions are selected from the examined solutions, and the next sets are then considered. With this procedure, the multi-objective optimization of multiple set functions can be conducted with reasonable computational costs. This paper defines a new class of greedy algorithms which includes the proposed nondominated-solution-based multi-objective greedy algorithm and the group greedy algorithm, and the characteristics of those algorithms are theoretically discussed. Then, the proposed method is applied to the sensor selection problem and its performance is evaluated. The results of the test case show that the proposed method not only gives the Pareto-optimal front of the multi-objective optimization problem but also produces sets of sensors in terms of D-, A-, and E-optimality, that are superior to the sets selected by pure greedy methods that consider only a single objective function.

关键词： Indexes Optimization Linear programming Signal processing algorithms greedy algorithms Search problems Relaxation methods greedy algorithm multi-objective optimization nondominated solution pareto front optimal experimental design data-driven sensor selection

来源：评论

学校读者我要写书评

暂无评论

Priority algorithms with advice for disjoint path allocation problems

引用

THEORETICAL COMPUTER SCIENCE 2024年 1021卷

作者： Bockenhauer, Hans-Joachim Frei, Fabian Horvath, Silvan Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Swiss Fed Inst Technol Dept Math Zurich Switzerland

We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. Like an online algorithm, a priority algorithm receives its input sequentially and must output irrevocable decisions for individual input items before having seen the entire input. However, in contrast to the online setting, a priority algorithm may choose an order on the set of all possible input items and the actual input is then presented according to this order. A priority algorithm is thus a natural model for the intuitively well-understood concept of a greedy algorithm. Mainly motivated by their application for proving lower bounds, we also consider priority algorithms with advice, thus measuring the necessary amount of information about the yet unknown parts of the input. Besides considering the classical variant of the DPA problem on paths and the related problem of Length-Weighted DPA, we mainly focus on DPA on trees. We show asymptotically matching upper and lower bounds on the advice necessary for optimality in LWDPA and generalize the known optimality result for DPA on paths to trees with maximal degree at most 3. On trees with higher maximal degree, we prove matching upper and lower bounds on the approximation ratio in the advice-free priority setting as well as upper and lower bounds on the advice necessary to achieve optimality.

关键词： Disjoint path allocation Priority algorithms Advice complexity greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：