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

20th International Conference on Electrical Machines (ICEM)

作者： Amoiralis, E. I. Tsili, M. A. Kladas, A. G. Univ Mil Educ Hellen Army Acad Sector Math & Engn Sci Dept Mil Sci Vari 16673 Greece Natl Tech Univ Athens Fac Elect & Comp Engn Athens GR-15780 Greece

ISBN: (纸本)9781467301428

The present paper compares the application of one deterministic and three non-deterministic optimization algorithms to global transformer design optimization. One deterministic optimization algorithm (Mixed Integer Nonlinear Programming), is compared to three non-deterministic approaches (Harmony Search, Differential Evolution and Genetic Algorithm). The comparison yields significant conclusions on the efficiency of the algorithms and the selection of the most suitable for the transformer design optimization problem.

关键词： transformers design optimization deterministic algorithms non-deterministic algorithms mixed integer nonlinear programming harmony search differential evolution genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved deterministic algorithms for Non-monotone Submodular Maximization 28th

Improved Deterministic Algorithms for Non-monotone Submodula...

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Sun, Xiaoming Zhang, Jialin Zhang, Shuo Zhang, Zhijie Chinese Acad Sci Inst Comp Technol Beijing Peoples R China Univ Chinese Acad Sci Sch Comp Sci & Technol Beijing Peoples R China

ISBN: (纸本)9783031221040;9783031221057

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 - o(1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio.

关键词： Submodular maximization deterministic algorithms Matroid constraint Knapsack constraint

来源：评论

学校读者我要写书评

暂无评论

deterministic algorithms for Submodular Maximization Problems 16

Deterministic Algorithms for Submodular Maximization Problem...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Niv Buchbinder Moran Feldman Department of Statistics and Operations Research Tel Aviv University School of Computer and Communication Sciences

ISBN: (纸本)9781510819672

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

关键词： Randomisation deterministic algorithms algorithms computer science

来源：评论

学校读者我要写书评

暂无评论

deterministic algorithms for the Lovasz Local Lemma 10

Deterministic Algorithms for the Lovasz Local Lemma

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Karthekeyan Chandrasekaran Navin Goyal Bernhard Haeupler Georgia Institute of Technology Microsoft Research Massachusetts Insititute of Technology

ISBN: (纸本)9780898717013

The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d≤2~k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser.

关键词： deterministic algorithms low light Lemma formula Probability Theory Nonzero Probability of disjoint events Probability of whole sample space Probability of null event randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved deterministic algorithms for non-monotone submodular maximization

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Sun, Xiaoming Zhang, Jialin Zhang, Shuo Zhang, Zhijie Chinese Acad Sci Inst Comp Technol State Key Lab Processors Beijing Peoples R China Univ Chinese Acad Sci Sch Comp Sci & Technol Beijing Peoples R China Fuzhou Univ Ctr Appl Math Fujian Prov Sch Math & Stat Fuzhou Peoples R China

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular *** this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 - ��(1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1/6 - �� approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.

关键词： Submodular maximization deterministic algorithms Derandomization Twin greedy Multiplicative updates

来源：评论

学校读者我要写书评

暂无评论

COMPARISON OF THE EFFICIENCY OF deterministic AND STOCHASTIC algorithms FOR VISUAL RECONSTRUCTION

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1989年第1期11卷 2-12页

作者： BLAKE, A Dept. of Comput. Sci. Edinburgh Univ. UK

Piecewise continuous reconstruction of real-valued data can be formulated in terms of nonconvex optimization problems. Both stochastic and deterministic algorithms have been devised to solve them. The simplest such reconstruction process is the weak string. Exact solutions can be obtained for it and are used to determine the success or failure of the algorithms under precisely controlled conditions. It is concluded that the deterministic algorithm (graduated nonconvexity) outstrips stochastic (simulated annealing) algorithms both in computational efficiency and in problem-solving power.

关键词： Stochastic processes Simulated annealing Computational modeling Problem-solving Noise reduction Image motion analysis Computer science Glands Testing Biomembranes INSPEC: Controlled Indexing optimisation computer vision computerised picture processing INSPEC: Non-Controlled Indexing problem-solving power deterministic algorithms stochastic algorithms visual reconstruction nonconvex optimization weak string computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Improved deterministic algorithms for Linear Programming in Low Dimensions 16

Improved Deterministic Algorithms for Linear Programming in ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Timothy M. Chan Cheriton School of Computer Science University of Waterloo

ISBN: (纸本)9781510819672

At SODA'93, Chazelle and Matousek presented a derandomization of Clarkson's sampling-based algorithm [FOCS'88] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o(1))dn with subsequent work by Bronnimann, Chazelle, and Matousek [FOCS'93]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids ε-approximations and runs in d~((3+o(1))d)n time. We then describe a few additional ideas that eventually improve the deterministic time bound to d~((1/2+o(1))d)n.

关键词： deterministic algorithms linear programming deterministic dimensions Bound

来源：评论

学校读者我要写书评

暂无评论

EXPERIMENTS WITH RANDOMIZED AND deterministic ROUTING algorithms ON TRANSPUTER NETWORKS

EXPERIMENTS WITH RANDOMIZED AND DETERMINISTIC ROUTING ALGORI...

引用

IEEE Singapore International Conference on Networks/International Conference on Information Engineering 93 - Communications and Networks for the Year 2000

作者： CAI, WT NANYANG TECHNOL UNIV SCH APPL SCIDIV COMP TECHNOLSINGAPORE 2263SINGAPORE

ISBN: (纸本)078031445X

An interprocessor communication scheme is a key to exploit parallel computers effectively. One of the efficient communication schemes on hypercubes is the two-phased randomized routing algorithm. In this paper, the performance of this randomized routing algorithm is studied. In addition, the performance of a deterministic routing algorithm, the greedy routing algorithm is evaluated.

关键词： transputer systems randomised algorithms deterministic algorithms hypercube networks performance evaluation telecommunication network routing transputer networks interprocessor communication scheme parallel computers hypercubes two-phased randomized routing algorithm performance deterministic routing algorithm greedy routing algorithm

来源：评论

学校读者我要写书评

暂无评论

Benchmarking Derivative-Free Global Optimization algorithms Under Limited Dimensions and Large Evaluation Budgets

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2025年第1期29卷 187-204页

作者： Stripinis, Linas Kudela, Jakub Paulavicius, Remigijus Vilnius Univ Inst Data Sci & Digital Technol LT-08663 Vilnius Lithuania Brno Univ Technol Inst Automat & Comp Sci Brno 61600 Czech Republic

This article addresses the challenge of selecting the most suitable optimization algorithm by presenting a comprehensive computational comparison between stochastic and deterministic methods. The complexity of algorithm selection arises from the absence of a universal algorithm and the abundance of available options. Manual selection without comprehensive studies can lead to suboptimal or incorrect results. In order to address this issue, we carefully selected 25 promising and representative state-of-the-art algorithms from both aforementioned classes. The evaluation with up to the 20 dimensions and large evaluation budgets $(10<^>{5}{\times }n)$ was carried out in a significantly expanded and improved version of the DIRECTGOLib v2.0 library, which included ten distinct collections of primarily continuous test functions. The evaluation covered various aspects, such as solution quality, time complexity, and function evaluation usage. The rankings were determined using statistical tests and performance profiles. When it comes to the problems and algorithms examined in this study, EA4eig, EBOwithCMAR, APGSK-IMODE, 1-DTC-GL, OQNLP, and DIRMIN stand out as superior to other derivative-free solvers in terms of solution quality. While deterministic algorithms can locate reasonable solutions with comparatively fewer function evaluations, most stochastic algorithms require more extensive evaluation budgets to deliver comparable results. However, the performance of stochastic algorithms tends to excel in more complex and higher-dimensional problems. These research findings offer valuable insights for practitioners and researchers, enabling them to tackle diverse optimization problems effectively.

关键词： Optimization Partitioning algorithms Evolutionary computation Benchmark testing Stochastic processes Linear programming Closed box Derivative-free global optimization deterministic algorithms evolutionary computation (EC) algorithms nature-inspired meta-heuristics numerical benchmarking

来源：评论

学校读者我要写书评

暂无评论

Mobile Agents on Chordal Graphs: Maximum Independent Set and Beyond 21st

Mobile Agents on Chordal Graphs: Maximum Independent Set and...

引用

21st International Conference on Distributed Computing and Intelligent Technology

作者： Kaur, Tanvir Paul, Kaustav Mondal, Kaushik Indian Inst Thelmol Ropar Rupnagar Punjab India

ISBN: (纸本)9783031814037;9783031814044

We consider the problem of finding a maximum independent set (MaxIS) of chordal graphs using mobile agents. Suppose n agents are initially placed arbitrarily on the nodes of an n-node chordal graph G = (V, E). Agents need to find a maximum independent set M of G such that each node of M is occupied by at least one agent. Also, each of the n agents must know whether its occupied node is a part of M or not. Starting from both rooted and arbitrary initial configuration, we provide distributed algorithms for n mobile agents having O(log n) memory each to compute the MaxIS of G in O(mnlog Delta) time, where m denotes the number of edges in G and Delta is the maximum degree of the graph. Agents do not need prior knowledge of any parameters if the initial configuration is rooted. For arbitrary initial configuration, agents need to know few global parameters beforehand. We further show that using a similar approach it is possible to find the maximum clique in chordal graphs and color any chordal graph with the minimum number of colors. We also provide a dynamic programming-based approach to solve the MaxIS finding problem in trees in O(n) time.

关键词： Mobile agents Maximum Independent Set Distributed algorithms deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：