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

Minimization Problems with Non-Submodular Cover Constraint

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第5期40卷 2340012-2340012页

作者： Wang, Wenqi Liu, Zhicheng Du, Donglei Shi, Peihao Zhang, Xiaoyan Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 9Y2 Canada Ind Technol Res Inst Co Ltd Nanjing Kinghua Operat Res & ArtificialIntelligenc Nanjing 210035 Peoples R China

The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovasz extension, we devise greedy and primal-dual approximation algorithms for these problems.

关键词： Approximation algorithm submodular function combinatorial optimization greedy algorithm primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

Novel algorithms for sequential fault diagnosis based on greedy method

引用

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART O-JOURNAL OF RISK AND RELIABILITY 2020年第6期234卷 779-792页

作者： Tian, Heng Duan, Fuhai Sang, Yong Fan, Liang Henan Univ Sci & Technol Sch Mechatron Engn Luoyang Peoples R China Dalian Univ Technol Sch Mech Engn 2 Linggong Rd Dalian 116024 Peoples R China AVIC Xian Flight Automat Control Res Inst Aviat Key Lab Sci & Technol Inertia Xian Peoples R China

Test sequencing for binary systems is a nondeterministic polynomial-complete problem, where greedy algorithms have been proposed to find the solution. The traditional greedy algorithms only extract a single kind of information from the D-matrix to search the optimal test sequence, so their application scope is limited. In this study, two novel greedy algorithms that combine the weight index for fault detection with the information entropy are introduced for this problem, which are defined as the Mix1 algorithm and the Mix2 algorithm. First, the application scope for the traditional greedy algorithms is demonstrated in detail by stochastic simulation experiments. Second, two new heuristic formulas are presented, and their scale factors are determined. Third, an example is used to show how the two new algorithms work, and four real-world D-matrices are employed to validate their universality and stability. Finally, the application scope of the Mix1 and Mix2 algorithms is determined based on stochastic simulation experiments, and the two greedy algorithms are also used to improve a multistep look-ahead heuristic algorithm. The Mix1 and Mix2 algorithms can obtain good results in a reasonable time and have a wide application scope, which also can be used to improve the multistep look-ahead heuristic algorithm.

关键词： D-matrix greedy algorithm information entropy sequential fault diagnosis test sequence

来源：评论

学校读者我要写书评

暂无评论

Tight Analysis of Parallel Randomized greedy MIS

引用

ACM TRANSACTIONS ON algorithmS 2020年第1期16卷 6-6页

作者： Fischer, Manuela Noever, Andreas Swiss Fed Inst Technol Univ Str 6 CH-8092 Zurich Switzerland

We provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA'12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS'87], and the previously best known bounds were O(log n) rounds in expectation for Erdos-Renyi random graphs by Calkin and Frieze [Random Struc. Alg.'90] and O(log(2) n) rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA'12]. We prove a high probability upper bound of O(log n) on the round complexity of this algorithm in general graphs and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC'85, JALG'86].

关键词： PRAM parallel algorithms greedy algorithm maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Revisiting the Prefer-same and Prefer-opposite de Bruijn sequence constructions

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 73-77页

作者： Alhakim, Abbas Sala, Evan Sawada, Joe

We present a simple greedy algorithm to construct the prefer-same de Bruijn sequence and prove that it is equivalent to the more complex algorithm first stated by Eldert et al. without proof (Eldert et al., 1958 [3]), and later by Fredricksen (Fredricksen, 1982 [5]). Then we prove that the resulting sequence has the lexicographically largest run-length representation among all de Bruijn sequences. Furthermore, we prove that the sequence resulting from a prefer-opposite greedy construction has the lexicographically smallest run length representation among all de Bruijn sequences. (C) 2020 Elsevier B.V. All rights reserved.

关键词： De Bruijn sequence Run-length greedy algorithm Prefer-same Prefer-opposite

来源：评论

学校读者我要写书评

暂无评论

Maximizing influence via link prediction in evolving networks

引用

ARRAY 2024年 24卷

作者： Zhang, Kexin Li, Mo Teng, Shuang Li, Lingling Wang, Yi Zhao, Xuezhuan Di, Jinhong Zhang, Ji Zhengzhou Univ Aeronaut Sch Elect & Informat Zhengzhou 450046 Peoples R China Liaoning Univ Sch Informat Shenyang 110036 Peoples R China Henan Yuanfang Human Digital Technol Serv Grp Co L Zhengzhou 450000 Peoples R China Zhengzhou Univ Aeronaut Zhengzhou 450046 Peoples R China Zhengzhou Univ Aeronaut Sch Comp Sci Zhengzhou 450046 Peoples R China Univ Southern Queensland Sch Math Phys & Comp Toowoomba 4350 Australia

Influence Maximization (IM), targeting the optimal selection of k seed nodes to maximize potential information dissemination in prospectively social networks, garners pivotal interest in diverse realms like viral marketing and political discourse dissemination. Despite receiving substantial scholarly attention, prevailing research predominantly addresses the IM problem within the confines of existing networks, thereby neglecting the dynamic evolutionary character of social networks. An inevitable requisite arises to explore the IM problem in social networks of future contexts, which is imperative for certain application scenarios. In this light, we introduce a novel problem, Influence Maximization in Future Networks (IMFN), aimed at resolving the IM problem within an anticipated future network framework. We establish that the IMFN problem is NP-hard and advocate a prospective solution framework, employing judiciously selected link prediction methods to forecast the future network, and subsequently applying a greedy algorithm to select the k most influential nodes. Moreover, we present SCOL (Sketch-based Cost-effective lazy forward selection algorithm Optimized with Labeling technique), a well-designed algorithm to accelerate the query of our IMFN problem. Extensive experimental results, rooted in five real-world datasets, are provided, affirming the efficacy and efficiency of the proffered solution and algorithms.

关键词： Influence maximization Future networks Link prediction greedy algorithm Graph query

来源：评论

学校读者我要写书评

暂无评论

Construction of minimum edge-fault tolerant connected dominating set in a general graph

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第2期45卷 63-63页

作者： Zhang, Yaoyao Zhang, Zhao Du, Ding-Zhu Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Zhejiang Normal Univ Sch Math Sci Jinhua 321004 Zhejiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

The Minimum connected dominating set problem (MinCDS) is a classical combinatorial optimization problem and has attached a lot of attention due to its application in wireless sensor networks (WSNs). Although the minimum k-connected m-fold dominating set problem (Min(k, m)-CDS), which takes vertex fault tolerance into consideration, has been extensively studied in recent years, studies on edge fault tolerant CDS only start very recently. In this paper, we study the edge analog of Min(k, m)-CDS, denoted as Min(k, m)-ECDS, which aims to find S subset of V(G) such that the subgraph of G induced by S is k-edge connected and for any v is an element of V \ S, there are at least m edges between v and S. We give a greedy algorithm for Min(k, m)- ECDS on a general graph, with a theoretically guaranteed approximation ratio at most (2k - 1) ln delta + O(1), where A is the maximum degree of G. When applied on an unit disk graph (UDG), the approximation ratio is at most 10k - 5/k + O(1) when m <= 5 and 14k + O(1) when m > 5. In particular, our algorithm on Min(2, 2)-ECDS has approximation ratio at most 23.5, which improves the ratio 30.51 obtained in Liang et al. (Wirel Commun Mob Comput, 2021).

关键词： Edge fault tolerance Connected dominating set greedy algorithm Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Training Sample Selection Strategy Applied to CNN in Magneto-Thermal Coupled Analysis

引用

IEEE TRANSACTIONS ON MAGNETICS 2021年第6期57卷 1-4页

作者： Gong, Ruohan Tang, Zuqi Univ Lille Arts & Metiers Inst Technol Cent Lille ULR 2697L2EPJunia F-59000 Lille France

Deep learning (DL) has attracted more and more attention in computational electromagnetism. Particularly, the convolutional neural network (CNN) is one of the most popular learning models in DL due to its excellent capacity for feature extraction and convergence. The efficiency of CNN mainly depends on how many training samples are needed to effectively converge the network. The sample preparation process often involves a lot of numerical computations, which can be very expensive and time-consuming. In this article, based on the traditional DL network training procedure, two different approaches, namely adding smart training samples and reference samples, are proposed to help the DL network converge. The smart sample selection is based on a greedy algorithm, which can be applied for both training and reference samples. The influences of these two approaches on the CNN training process are investigated by an example of the coupled magneto-thermal computation applied to a transformer. Numerical results show that the two proposed approaches can significantly help the network to converge and improve the efficiency of the DL model.

关键词： Convolutional neural network (CNN) coupled magneto-thermal problem deep learning greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

A greedy reduced basis scheme for multifrequency solution of structural acoustic systems

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 2020年第2期121卷 187-200页

作者： Baydoun, Suhaib Koji Voigt, Matthias Jelich, Christopher Marburg, Steffen Tech Univ Munich Dept Mech Engn Chair Vibroacoust Vehicles & Machines Boltzmannstr 15 D-85748 Garching Germany Tech Univ Berlin Inst Math Berlin Germany

The solution of frequency dependent linear systems arising from the discretization of vibro-acoustic problems requires a significant computational effort in the case of rapidly varying responses. In this paper, we review the use of a greedy reduced basis scheme for the efficient solution in a frequency range. The reduced basis is spanned by responses of the system at certain frequencies that are chosen iteratively based on the response that is currently worst approximated in each step. The approximations at intermediate frequencies as well as the a posteriori estimations of associated errors are computed using a least squares solver. The proposed scheme is applied to the solution of an interior acoustic problem with boundary element method (BEM) and to the solution of coupled structural acoustic problems with finite element method and BEM. The computational times are compared to those of a conventional frequencywise strategy. The results illustrate the efficiency of the method.

关键词： boundary element method greedy algorithm multifrequency reduced basis structural acoustic interaction

来源：评论

学校读者我要写书评

暂无评论

Planning centralised logistics of products with specific characteristics under extreme situations, sudden changes and dynamic conditions

引用

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE-OPERATIONS & LOGISTICS 2024年第1期11卷

作者： Altinoz, Okkes Tolga Ankara Univ Dept Elect & Elect Engn Golbasi 50 Yil Campus TR-06830 Golbasi Ankara Turkiye

A prominent situation in the transportation of goods to their destination is the need for unexpected changes to predetermined routes. In addition, when transporting goods to units with urgent needs have to be met. This problem of rerouting multiple vehicles under extreme situations when a route change is investigated in this paper. The delivery of medical products to nodes carrying infectious diseases is chosen as a case study whereas the vehicles visit each unit, the risk of contamination increases, and the vehicles need to meet the needs of the most urgent units first. For this case study, a modified test data is generated for dynamic problem, and it is solved with two-layered framework. The first layer is the static layer that the initial route is planned, and the second layer is the re-optimisation layer that is solved by using the proposed algorithm named as evolutionary algorithm operator-based Hybrid Genetic and greedy algorithm (EAO-GA2). The proposed algorithm for the two layer frameworks studied in this research gave 83% better results than the problems solved for the static problem, and the total distance change in the dynamic problems studied was only 1.06%.

关键词： Logistics optimisation dynamic vehicle routing problem genetic algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Structural Optimization of an Electromagnetic Actuator Based on Genetic algorithm, greedy Search and Their Combination 28

Structural Optimization of an Electromagnetic Actuator Based...

引用

28th IEEE International Symposium on Industrial Electronics (IEEE-ISIE)

作者： Ruzbehi, Shabnam Hahn, Ingo Univ Erlangen Nurnberg Inst Elect Drives & Machines Erlangen Germany

ISBN: (纸本)9781728136660

In the last years, optimal operation and usage of electrical machines leads to an increased attention for improving the operating behaviour and changes in the electrical machine's structure for industrial applications. In conventional optimization, it is common to use parametric design and geometric optimization, but this manuscript presents the structural or topological optimization. This method gives more freedom to the designers to adapt high performance electrical machines to the customer goals. The implementation of the proposed method for structural design and topology optimization is applied to the detailed design of an electromagnetic actuator. In general, electrical machinery is aimed to produce high torque and power at minimum weight to gain a high torque and power density. Therefore, high force or torque and low weight are the two main goals in this work for designing electrical machines, which can satisfy mechanical, structural and magnetic constraints. To show the validity and the opportunities of the proposed optimization method, the design of a simple magnetic actuator using a metaheuristic global optimization method (genetic algorithm (GA)) and a deterministic local search (greedy algorithm) is investigated at first and, secondly, a combination of both of these methods is presented for a highly nonlinear problem. The given design goals have been successfully achieved using the proposed structural optimization method to find the best suited topology.

关键词： topology optimization genetic algorithms metaheuristic algorithm greedy algorithm local optimization global optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：