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

A complete anytime algorithm for number partitioning

ARTIFICIAL INTELLIGENCE 1998年第2期106卷 181-203页

作者： Korf, RE Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

Given a set of numbers, the two-way number partitioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible. The problem is NP-complete. Based on a polynomial-time heuristic due to Karmarkar and Karp, we present a new algorithm, called Complete Karmarkar-Karp (CKK), that optimally solves the general number-partitioning problem, and significantly outperforms the best previously-known algorithms for large problem instances. For numbers with twelve significant digits or less, CKK can optimally solve two-way partitioning problems of arbitrary size in practice. For numbers with greater precision, CKK first returns the Karmarkar-Karp solution, then continues to find better solutions as time allows. Over seven orders of magnitude improvement in solution quality is obtained in less than an hour of running time. Rather than building a single solution one element at a time, or modifying a complete solution, CKK constructs subsolutions, and combines them together in all possible ways. This approach may be effective for other NP-hard problems as well. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： number partitioning anytime algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Effective anytime algorithm for multiobjective combinatorial optimization problems

引用

INFORMATION SCIENCES 2021年 565卷 210-228页

作者： Angel Dominguez-Rios, Miguel Chicano, Francisco Alba, Enrique Univ Malaga ITIS Software Malaga Spain

In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions can be computed in a short time and the search algorithm has to be stopped prematurely to analyze the solutions found so far. A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. However, just a few exact algorithms in the literature exist with the ability to provide such a well-spread set of solutions at any moment: we call them anytime algorithms. We propose a new exact anytime algorithm for multiobjective combinatorial optimization combining three novel ideas to enhance the anytime behavior. We compare the proposed algorithm with those in the state-of-the-art for anytime multiobjective combinatorial optimization using a set of 480 instances from different well-known benchmarks and four different performance measures: the overall non-dominated vector generation ratio, the hypervolume, the general spread and the additive epsilon indicator. A comprehensive experimental study reveals that our proposal outperforms the previous algorithms in most of the instances. (c) 2021 Elsevier Inc. All rights reserved.

关键词： Multiobjective combinatorial optimization anytime algorithm Well-spread non-dominated points

来源：评论

学校读者我要写书评

暂无评论

Efficient anytime algorithm for large-scale QoS-aware web service composition

引用

INTERNATIONAL JOURNAL OF WEB AND GRID SERVICES 2013年第1期9卷 82-106页

作者： Kil, Hyunyoung Nam, Wonhong Korea Univ Res Inst Comp Informat & Commun Seoul 136701 South Korea Konkuk Univ Dept Internet & Multimedia Engn Seoul 143701 South Korea

The QoS-aware web service composition (WSC) problem aims at the fully automatic construction of a composite web service with the optimal accumulated QoS value. It is, however, intractable to solve the QoS-aware WSC problem for large scale instances since the problem corresponds to a global optimisation problem. That is, in the real world, traditional algorithms can require significant amount of time to finally find the optimal solution, and such an unexpected long delay is unfavourable to users. In this paper, we propose a novel anytime algorithm using dynamic beam widths for the QoS-aware WSC problem. Our algorithm generates early sub-optimal solutions and keeps improving the quality of the solution along with the execution time, up to the optimal solution if a client allows enough time. We empirically validate that our algorithm can identify composite web services with high quality much earlier than an optimal algorithm and the beam stack search.

关键词： anytime algorithm web service composition QoS quality of services optimisation

来源：评论

学校读者我要写书评

暂无评论

A Space-Bounded anytime algorithm for the Multiple Longest Common Subsequence Problem

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第11期26卷 2599-2609页

作者： Yang, Jiaoyun Xu, Yun Shang, Yi Chen, Guoliang Univ Sci & Technol China Key Lab High Performance Comp Hefei Anhui Peoples R China Univ Sci & Technol China Sch Comp Sci Hefei Anhui Peoples R China Univ Missouri Dept Comp Sci Columbia MO 65211 USA

The multiple longest common subsequence (MLCS) problem, related to the identification of sequence similarity, is an important problem in many fields. As an NP-hard problem, its exact algorithms have difficulty in handling large-scale data and time-and space-efficient algorithms are required in real-world applications. To deal with time constraints, anytime algorithms have been proposed to generate good solutions with a reasonable time. However, there exists little work on space-efficient MLCS algorithms. In this paper, we formulate the MLCS problem into a graph search problem and present two space-efficient anytime MLCS algorithms, SA-MLCS and SLA-MLCS. SA-MLCS uses an iterative beam widening search strategy to reduce space usage during the iterative process of finding better solutions. Based on SA-MLCS, SLA-MLCS, a space-bounded algorithm, is developed to avoid space usage from exceeding available memory. SLA-MLCS uses a replacing strategy when SA-MLCS reaches a given space bound. Experimental results show SA-MLCS and SLA-MLCS use an order of magnitude less space and time than the state-of-the-art approximate algorithm MLCS-APP while finding better solutions. Compared to the state-of-the-art anytime algorithm Pro-MLCS, SA-MLCS and SLA-MLCS can solve an order of magnitude larger size instances. Furthermore, SLA-MLCS can find much better solutions than SA-MLCS on large size instances.

关键词： Heuristic search anytime algorithm space bounded multiple longest common subsequence (MLCS)

来源：评论

学校读者我要写书评

暂无评论

LOGIC PROGRAMMING, ABDUCTION AND PROBABILITY - A TOP-DOWN anytime algorithm FOR ESTIMATING PRIOR AND POSTERIOR PROBABILITIES

引用

NEW GENERATION COMPUTING 1993年第3-4期11卷 377-400页

作者： POOLE, D CANADIAN INST ADV RES TORONTOONCANADA

Probabilistic Horn abduction is a simple framework to combine probabilistic and logical reasoning into a coherent practical framework. The numbers can be consistently interpreted probabilistically, and all of the rules can be interpreted logically. The relationship between probabilistic Horn abduction and logic programming is at two levels. At the first level probabilistic Horn abduction is an extension of pure Prolog, that is useful for diagnosis and other evidential reasoning tasks. At another level, current logic programming implementation techniques can be used to efficiently implement probabilistic Horn abduction. This forms the basis of an ''anytime'' algorithm for estimating arbitrary conditional probabilities. The focus of this paper is on the implementation.

关键词： PROBABILISTIC HORN ABDUCTION BAYESIAN NETWORKS anytime algorithm LOGIC PROGRAMMING CONTINUATIONS

来源：评论

学校读者我要写书评

暂无评论

Advantages of anytime algorithm for Multi-Objective Query Optimization 18

Advantages of Anytime Algorithm for Multi-Objective Query Op...

引用

18th IEEE World Symposium on Applied Machine Intelligence and Informatics (SAMI)

作者： Rituraj, Rituraj Koczy, Annamaria R. Varkonyi Obuda Univ Doctoral Sch Appl Informat & Appl Math Becsi U 96-B H-1034 Budapest Hungary Obuda Univ Inst Automat Kando Kalman Fac Elect Engn Becsi U 96-B H-1034 Budapest Hungary

ISBN: (纸本)9781728131498

Data is becoming an important source of information these days. According to the recent Forbes survey, there are 2.5 quintillion bytes of data created each day at our current pace. While getting these amounts of data, it is necessary to process them in order to extract information. These data can be accessed in many ways in order to get meaningful information. This paper only deals with the query plans model through multi-objective optimization process using anytime algorithm. Query plans is an ordered stairway used for accessing data in SQL relational database systems. Query plans provides diverse tradeoff between conflicting cost matrices. The cost matrices are execution time, energy consumption and execution fees in multi-objective aspects. When SQL database run the queries by choosing an optimum query execution plan then it minimizes the query cost, which is very crucial for the query optimizer. Multi-objective query optimization and anytime algorithm possess very specific properties in order to support an interactive process which dynamically add various constraints and then finally select the best plan based on the continuously refined visualization of optimal cost tradeoffs. First, the anytime algorithms generate the multiple result plan sets which increase the quality with low latency rate between consecutive results. Second, the consecutive results will be incremented to avoid regenerating query plans when being invoked several times for the same query but with different user constraints. This paper deals with the advantages of anytime algorithm for the multi objective query optimization to analyze the complexity which offers an attractive tradeoff between the results. It can be used to update frequency, single invocation time complexity and multiple time over invocations. These properties make anytime algorithm suitable to be used within an interactive query optimization process.

关键词： Query plans Multi-objective optimization anytime algorithm

来源：评论

学校读者我要写书评

暂无评论

An anytime algorithm for Camera-Based Character Recognition

An Anytime Algorithm for Camera-Based Character Recognition

引用

12th International Conference on Document Analysis and Recognition (ICDAR)

作者： Kobayashi, Takuya Iwamura, Masakazu Matsuda, Takahiro Kise, Koichi Osaka Prefecture Univ Grad Sch Engn Sakai Osaka Japan

ISBN: (纸本)9780769549993

In a scene image, some characters are difficult to recognize and some others are recognized easily. Such difficult characters usually make the processing time long while easy characters are recognized in a short time. In this paper, we propose a system which recognizes each character with a proper cost for the difficulty. Through the process, easy characters are recognized early and difficult ones are recognized late. This is a desired property of an anytime algorithm that the recognition accuracy does not decrease as the time increases. In order to realize it, we propose a method which splits the recognition process into several times and accumulates the recognition results and extracted features. We also discuss what is required to realize the anytime algorithm for the scene character recognition task. Experiments reveal that the proposed method obtains recognition results of easy characters earlier than the conventional method.

关键词： scene character recognition anytime algorithm local feature ASIFT tracking video input

来源：评论

学校读者我要写书评

暂无评论

A statistical anytime algorithm for the Halting Problem

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2020年第2期9卷 155-166页

作者： Calude, Cristian S. Dumitrescu, Monica Univ Auckland Dept Comp Sci Auckland New Zealand Bucharest Univ Fac Math & Comp Sci Bucharest Romania

In a previous paper we used computer running times to define a class of computable probability distributions on the set of halting programs and developed a probabilistic anytime algorithm for the Halting Problem. The choice of a computable probability distribution - essential for the algorithm - can be rather subjective and hard to substantiate. In this paper we propose and study an efficient statistical anytime algorithm for the Halting Problem. The main advantage of the statistical algorithm is that it can be implemented without any prior information about the running times on the specific model of computation and the cut-off temporal bound is reasonably small. The algorithm has two parts: the pre-processing which is done only once (when the parameters of the quality of solutions are fixed) and the main part which is run for any input program. With a confidence level as large as required, the algorithm produces correct decisions with a probability as large as required. Three implementations of the algorithm are presented and numerically illustrated.

关键词： Halting Problem anytime algorithm running time order statistics

来源：评论

学校读者我要写书评

暂无评论

A Survey of Usage of anytime algorithm in Fault detection in Cloud Systems 21

A Survey of Usage of Anytime Algorithm in Fault detection in...

引用

IEEE 21st World Symposium on Applied Machine Intelligence and Informatics (SAMI)

作者： Asadova, Farida R., Annamaria Varkonyi-Koczy, Y. Kertesz, Gabor Lovas, Robert Obuda Univ Sch Appl Informat & Appl Math Budapest Hungary Obuda Univ John von Neumann Fac Informat Budapest Hungary Eotvos Lorand Res Network ELKH Inst Comp Sci & Control SZTAKI Budapest Hungary

ISBN: (纸本)9798350319866

Fault detection, which requires a lot of time and complexity, is one of the most difficult tasks for cloud computing. In this research, we investigate the utilization of the anytime algorithm in cloud-based fault detection techniques. anytime algorithms are real-time decision-making algorithms that focus on time-deliberation. In this paper, the basic concepts of the anytime algorithm in existing works as well as its benefits of usage are analyzed. Various literature is reviewed and combined for possible fault recognition and time deliberation. The paper includes details of anytime processing in fault detection in different subject areas. Based on the survey, we aim to define the algorithm processing implementation as future work.

关键词： anytime algorithm Real-time decision making Fault detection Machine Learning Cloud Computing Artificial Agent Deep Learning

来源：评论

学校读者我要写书评

暂无评论

A probabilistic anytime algorithm for the halting problem

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2018年第2-3期7卷 259-271页

作者： Calude, Cristian S. Dumitrescu, Monica Univ Auckland Dept Comp Sci Auckland New Zealand Bucharest Univ Fac Math & Comp Sci Bucharest Romania

The Halting Problem, the most (in) famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions. Experimental results reported on various models of computation suggest that halting programs are not uniformly distributed - running times play an important role. A reason is that a program which eventually stops but does not halt "quickly", stops at a time which is algorithmically compressible. In this paper we work with running times to define a class of computable probability distributions on the set of halting programs in order to construct an anytime algorithm for the Halting problem with a probabilistic evaluation of the error of the decision.

关键词： Halting Problem anytime algorithm running time distribution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：