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

The Query Complexity of searching Trees with Permanently Noisy Advice

ACM Transactions on algorithms 2025年第2期21卷 1-30页

作者： Lucas Boczkowski Uriel Feige Amos Korman Yoav Rodeh IRIF CNRS and University of Paris Paris France Weizmann Institute of Science Rehovot Israel University of Haifa Haifa Israel and FILOFOCS CNRS Tel-Aviv Israel ORT Braude College Karmiel Israel

We consider a search problem on trees aiming to find a treasure that an adversary places at one of the nodes. The algorithm can query nodes and extract directional information from them. That is, each node holds a pointer, termed advice, to one of its neighbors. Ideally, this advice points to the neighbor that is closer to the treasure, however, with probability \(q\) this advice points to a uniformly random neighbor. Crucially, the advice is permanent, hence querying the same node again yields the same *** \(\Delta\) denote the maximal degree. Roughly speaking, we show that the expected number of queries incurs a phase transition when \(q\) is about \(1/\sqrt{\Delta}\). In a recent paper, at TALG’21, we showed that if \(q\) is above the threshold then the expected number of queries is polynomial in \(n\). Here, we prove that below the threshold, the expected number of queries is \(\mathcal{O}(\sqrt{\Delta}\log\Delta\cdot\log^{2}n)\), which is tight up to an \(\mathcal{O}(\log n)\) factor when \(\Delta\) is small. We further show that this factor can be reduced to \(\mathcal{O}(\log\log n)\) in the case of regular trees and assuming that \(q0\). In addition, we study the case that the treasure must be found with some given probability. We show that for every fixed \(\varepsilon,\delta>0\), if \(q<1/\Delta^{\varepsilon}\) then there exists a search strategy that with probability \(1-\delta\) finds the treasure using \((\delta^{-1}\log n)^{O(\frac{1}{\varepsilon})}\) queries, whereas \((\delta^{-1}\log n)^{\Omega(\frac{1}{\varepsilon})}\) queries are necessary.

关键词： search algorithms Fault-tolerance Noisy advice Randomized algorithms Trees

来源：评论

学校读者我要写书评

暂无评论

A Hybrid search Algorithm for Midterm Optimal Scheduling of Thermal Power Plants

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2015年第1期2015卷 1-13页

作者： Liao, Shengli Cheng, Chuntian Wang, Jing Feng, Zhongkai Dalian Univ Technol Inst Hydropower & Hydroinformat Dalian 116024 Peoples R China Huadian Elect Power Res Inst Hangzhou 310030 Zhejiang Peoples R China

A hybrid search algorithm consisting of three stages is presented to solve the midterm schedule for thermal power plants (MTSFTPP) problem, where the primary objective is to achieve equal accumulated operating hours of installed capacity (EAOHIC) for all thermal power plants during the selected period. First, feasible spaces are produced and narrowed based on constraints on the number of units and power load factors. Second, an initial feasible solution is obtained by a heuristic method that considers operating times and boundary conditions. Finally, the progressive optimality algorithm (POA), which we refer to as the vertical search algorithm (VSA), is used to solve the MTSFTPP problem. A method for avoiding convergence to a local minimum, called the lateral search algorithm (LSA), is presented. The LSA provides an updated solution that is used as a new feasible starting point for the next search in the VSA. The combination of the LSA and the VSA is referred to as the hybrid search algorithm(HSA), which is simple and converges quickly to the global minimum. The results of two case studies show that the algorithm is very effective in solving the MTSFTPP problem accurately and in real time.

关键词： search algorithms COMPUTER scheduling PROBLEM solving BOUNDARY value problems COMPUTER algorithms

来源：评论

学校读者我要写书评

暂无评论

Identification of Fuzzy Inference Systems by Means of a Multiobjective Opposition-Based Space search Algorithm

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-13页

作者： Huang, Wei Oh, Sung-Kwun Beihang Univ State Key Lab Virtual Real Technol & Syst Beijing 100191 Peoples R China Tianjin Univ Technol Sch Comp & Commun Engn Tianjin 300384 Peoples R China Univ Suwon Dept Elect Engn Gyeonggi Do 445743 Hwaseong Si South Korea

We introduce a new category of fuzzy inference systems with the aid of a multiobjective opposition-based space search algorithm (MOSSA). The proposed MOSSA is essentially a multiobjective space search algorithm improved by using an opposition-based learning that employs a so-called opposite numbers mechanism to speed up the convergence of the optimization algorithm. In the identification of fuzzy inference system, the MOSSA is exploited to carry out the parametric identification of the fuzzy model as well as to realize its structural identification. Experimental results demonstrate the effectiveness of the proposed fuzzy models.

关键词： FUZZY systems search algorithms MATHEMATICAL optimization SYSTEM analysis STOCHASTIC convergence

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Differential Evolution and Tree search Algorithm for the Job Shop Scheduling Problem

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2011年第1期2011卷 p1-20页

作者： Zhang, Rui Wu, Cheng Nanchang Univ Sch Econ & Management Nanchang 330031 Peoples R China Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. In terms of the objective function, most existing research has been focused on the makespan criterion. However, in contemporary manufacturing systems, due-date-related performances are more important because they are essential for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a hybrid differential evolution (DE) algorithm is proposed for the problem. To enhance the overall search efficiency, a neighborhood property of the problem is discovered, and then a tree search procedure is designed and embedded into the DE framework. According to the extensive computational experiments, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness objective.

关键词： DIFFERENTIAL evolution (Computer science) search algorithms PRODUCTION scheduling WORKING hours COMBINATORIAL optimization

来源：评论

学校读者我要写书评

暂无评论

Reliability-redundancy-location allocation with maximum reliability and minimum cost using search techniques

引用

INFORMATION AND SOFTWARE TECHNOLOGY 2017年 82卷 36-54页

作者： Qiu, Xiang Ali, Shaukat Yue, Tao Zhang, Li Design Inst Co Ltd China Mobile Grp Beijing Peoples R China Simula Res Lab Oslo Norway Univ Oslo Dept Informat Oslo Norway Beihang Univ Sch Comp Sci & Engn Beijing Peoples R China

Context: A safety critical system requires an automated and optimal allocation of redundant component instances to its existing components, including: 1) the selection of components (locations) on which the redundancy must be applied, 2) how many redundant component instances of varying reliability and cost should be allocated to each selected location. Objective: Our work aims to searching for the near optimal allocation solutions achieving the higher reliability of the system within the allowed cost. Such allocation must be made earlier, for example, while designing the architecture of the system to avoid unnecessary complexity of addressing unsafe situations discovered in the system development and deployment phases. Method: With the above objective in mind, we propose a search-based allocation approach based on the overall objectives of maximizing the overall system reliability and minimizing the cost of introducing and allocating redundancy structures to the system. The architecture of a system modeled using the Unified Modeling Language (UML) along with redundancy structures is encoded as an optimization problem. To guide a search algorithm to solve the problem, we propose a fitness function based on the two optimization objectives: high reliability and low cost. Results: We empirically evaluated the performance of four search algorithms (Genetic Algorithm, (1 +1) Evolutionary Algorithm, Alternating Variable Method (AVM) and Random search) together with the proposed fitness function on. 10 real-world Subsea Oil&Gas Production Systems of varying complexity. Results show that the AVM algorithm significantly outperforms the rest. Conclusion: Based on the results of empirical evaluation, we found that AVM can provide the best allocation of redundancy structures as compared to the rest of the algorithms. On average, AVM provided 0.008% of more reliability while saving 26.78% on allocation cost as compared to RS. Our novel solution based on the results of empirical

关键词： Reliability block diagram Redundancy structure search algorithms UML Optimization Empirical studies

来源：评论

学校读者我要写书评

暂无评论

Comparative performance assessment of a novel quasi-oppositional harmony search algorithm and internal model control method for automatic generation control of power systems

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2015年第11期9卷 1137-1150页

作者： Shiva, Chandan Kumar Mukherjee, Vivekananda Indian Sch Mines Dept Elect Engn Dhanbad 826004 Jharkhand India

This initiative work addresses the comparative performance assessment of a novel quasi-oppositional harmony search (QOHS) algorithm and internal model control (IMC) method, in the environment of automatic generation control. These two techniques are applied to a single-area non-reheat and reheat turbine with and without droop characteristic, and four-area hydro-thermal interconnected power system under various operating conditions. Later on, robustness analysis of both the two test systems is carried out by varying the speed regulating parameters, time constants of governor, turbine, power system and the gain of power system in the range of +/- 50% in case of single-area test system. In four-area test system, the same is carried out with the consonance of step load perturbation in different control area at distinct time-interval. Simulation results show that the proposed QOHS algorithm offers better dynamic control with robust performance as compared with IMC based approach. For on-line, off-nominal operating conditions, fast acting Sugeno fuzzy logic (SFL) is applied to obtain on-line dynamic responses of the studied power system model. Moreover, time-domain simulation of the investigated four-area test system reveals that the proposed QOHS-SFL based intelligent controller yields on-line, off-nominal controller parameters, resulting in on-line optimal dynamic response profile.

关键词： ELECTRIC power production search algorithms FUZZY logic HYDROTHERMAL electric power systems INTERCONNECTED electric utility systems

来源：评论

学校读者我要写书评

暂无评论

Guided search MIMO Detectors aided by Lattice Reduction under Correlated Channels

引用

IEEE LATIN AMERICA TRANSACTIONS 2015年第3期13卷 599-608页

作者： Mostagi, Y. M. Marinello Filho, J. C. Abrao, T. Univ Estadual Londrina Londrina Parana Brazil Univ Estadual Londrina Dept Elect Engn Commun Grp Londrina Parana Brazil

The conventional detector (matched filter) becomes inefficient in MIMO systems demanding high data throughput and/or subject to interference and/or under correlated channels. The bit error rate performance or system capacity under conventional detection will be substantially degraded when the spatial diversity provided by multiple antennas cannot be fully exploited and the detection process is unable to efficiently separate the signal from each antenna. The solution discussed in this paper seeks to establish more efficient detectors for MIMO systems with the aid of the Lattice Reduction technic. These detectors use information from the interfering signals in a way to improve the signal detection in the antenna of interest, thus providing advantages over the conventional system, at the expense of increasing complexity. The focus of this paper consists in comparing the characteristics of three sub-optimal detectors, previously analyzed in [1], based on the maximum-likelihood function and the guided search principle. Especially, the complexity vs performance trade-off for the sphere detector (SD), the QR decomposition-based detector (QRD) the greedy search detector (GSD) and its variants aided by the Lattice Reduction are compared. We have considered the performance-complexity tradeoff as a main figure-of-merit of sub-optimal MIMO detectors under Rayleigh correlated fading channels.

关键词： Multiuser coherent detection MIMO systems ML estimation sub-optimum detection search algorithms Lattice Reduction

来源：评论

学校读者我要写书评

暂无评论

Simple algorithm for partial quantum search

引用

QUANTUM INFORMATION PROCESSING 2006年第1期5卷 5-10页

作者： Korepin, Vladimir E. Grover, Lov K. SUNY Stony Brook CN Yang Inst Theoret Phys Stony Brook NY 11794 USA Bell Labs Lucent Technol Murray Hill NJ 07974 USA

Quite often in database search, we only, need to extract portion of the information about the satisfying item. We consider this problem in the following form the database of N items is separated into K blocks of size b = N/K elements each and an algorithm has just to find the block containing the item (of interest. The queries are exactly the same as in the standard database search problem. We present a quantum algorithm for this problem of partial search that takes about 0.34 root b fewer iterations than the quantum search algorithm.

关键词： quantum computation quantum algorithms search algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimization method based on Generalized Pattern search Algorithm to identify bridge parameters indirectly by a passing vehicle

引用

JOURNAL OF SOUND AND VIBRATION 2014年第2期333卷 364-380页

作者： Li, Wei-ming Jiang, Zhi-hui Wang, Tai-long Zhu, Hong-ping Wuhan Polytech Univ Sch Civil Engn & Architecture Wuhan 430023 Hubei Peoples R China Changsha Univ Sci & Technol Hunan Prov Res Ctr Safety Control Technol & Equip Changsha 410114 Hunan Peoples R China Huazhong Univ Sci & Technol Sch Civil Engn & Mech Wuhan 430074 Peoples R China

Generalized Pattern search Algorithm (GPSA) has rarely been investigated for structural health monitoring, but may have potential application in civil engineering, because it does not require any gradient information of the objective function. Meanwhile, indirect identification is an attractive concept that recognizes the bridge parameters by the vehicle responses. This paper proposes a theoretical indirect identification method based on optimization method, and the implementation is performed by the GPSA. Firstly, the GPSA theory is investigated, and a simple example is employed to describe the process of the algorithm. Secondly, a theoretical indirect identification method is proposed, based on the optimization method rather than the conventional transforms from time domain to frequency domain. The proposed method can identify the parameters of the vehicle bridge system, including the bridge stiffness and the 1st frequency. Based on the optimization method, the feasibility and accuracy of GPSA are demonstrated with 0.06% of errors. The GPSA shows good robustness in the identifications with various noise levels, and the maximum error is about 3.30% and can be accepted for the engineering application even with a SNR 5 noise level. The computation time relies only on the function evaluation times, and is not positively related to the noise level. Thirdly, the performance of GPSA is compared with that of Genetic Algorithm (GA). The accuracy of GPSA and GA are approximately equivalent with various noise levels. Compared with GA, GPSA needs fewer iterations and much fewer evaluations, therefore is more efficient in the identification with an almost consistent accuracy with various noise levels. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： GENERALIZATION search algorithms PARAMETER estimation STRUCTURAL health monitoring CIVIL engineering FREQUENCY-domain analysis

来源：评论

学校读者我要写书评

暂无评论

A Variable Neighborhood search Algorithm for the Leather Nesting Problem

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2012年第1期2012卷 1-28页

作者： Alves, Claudio Bras, Pedro Valerio de Carvalho, Jose M. Pinto, Telmo Univ Minho Escola Engn Ctr Invest Algoritmi P-4710057 Braga Portugal

The leather nesting problem is a cutting and packing optimization problem that consists in finding the best layout for a set of irregular pieces within a natural leather hide with an irregular surface and contour. In this paper, we address a real application of this problem related to the production of car seats in the automotive industry. The high quality requirements imposed on these products combined with the heterogeneity of the leather hides make the problem very complex to solve in practice. Very few results are reported in the literature for the leather nesting problem. Furthermore, the majority of the approaches impose some additional constraints to the layouts related to the particular application that is considered. In this paper, we describe a variable neighborhood search algorithm for the general leather nesting problem. To evaluate the performance of our approaches, we conducted an extensive set of computational experiments on real instances. The results of these experiments are reported at the end of the paper.

关键词： search algorithms LEATHER AUTOMOBILE industry MATHEMATICAL optimization BLOCK clubs NEIGHBORHOODS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：