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

On transitions in the behaviour of tabu search algorithm TabuCol for graph colouring

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE 2018年第1期30卷 53-69页

作者： Chalupa, D. Univ Hull Sch Engn & Comp Sci Comp Sci Kingston Upon Hull N Humberside England

Even though tabu search is one of the most popular metaheuristic search strategies, its understanding in terms of behavioural transitions and parameter tuning is still very limited. In this paper, we present a theoretical and experimental study of a popular tabu search algorithm TabuCol for graph colouring. We show that for some instances, there are sharp transitions in the behaviour of TabuCol, depending on the value of tabu tenure parameter. The location of this transition depends on graph structure and may also depend on its size. This is further supported by an experimental study of success rate profiles, which we define as an empirical measure of these transitions. We study the success rate profiles for a range of graph colouring instances, from 2-colouring of trees and forests to several instances from the DIMACS benchmark. These reveal that TabuCol may exhibit a spectrum of different behaviours ranging from simple transitions to highly complex probabilistic behaviour.

关键词： Tabu search TabuCol transitions graph colouring algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

PARALLEL MEAN SHIFT ACCURACY AND PERFORMANCE TRADE-OFFS 25

PARALLEL MEAN SHIFT ACCURACY AND PERFORMANCE TRADE-OFFS

引用

25th IEEE International Conference on Image Processing (ICIP)

作者： Duncan, Kirsty R. Stewart, Robert Michaelson, Greg Heriot Watt Univ Sch Math & Comp Sci Edinburgh Midlothian Scotland

ISBN: (纸本)9781479970612

This paper decomposes the algorithmic parameters that affect the accuracy and parallel run times of mean shift segmentation. Following Comaniciu and Meer [1], rather than perform calculations in the feature space of the image, the joint spatial-range domain is represented by the image space, with feature space information associated with each point. We report parallel speedup and segmentation accuracy using a standardised segmentation dataset and the Probabilistic Rand index (PRI) accuracy measure. Changes to the algorithmic parameters are analysed and a sweet spot between PRI and run time is found. Using a range window radius of 20, spatial window radius of 10 and threshold of 50, the PRI is improved by 0.17, an increase of 34% which is comparable to state of the art. Mean shift clustering run time is reduced by 97% with parallelism, a speedup of 32 on a 64-core CPU.

关键词： Image segmentation mean shift algorithm analysis parallel processing

来源：评论

学校读者我要写书评

暂无评论

Chessboard Cryptalgorithm 2

Chessboard Cryptalgorithm

引用

2nd International Conference on Advances in Electronics, Computers and Communications (ICAECC)

作者： Prajit, T. R. Ramaiah Inst Technol Dept Elect & Commun Bengaluru 54 India

ISBN: (纸本)9781538637852

Chessboard cryptalgorithm is an algorithm to encrypt N bit binary data using a key of size N. It provides unique mappings for each key and scrambles the sequence using an approach similar to the movement of the Queen on the chessboard. An important property is that the function for encryption and decryption is the same and not inverse as in typical cryptalgorithms. The number of combinations that can be generated is large and therefore to an extent, it protects against the brute force approach.

关键词： algorithm analysis cryptography network security encryption decryption

来源：评论

学校读者我要写书评

暂无评论

Hoare Logics for Time Bounds A Study in Meta Theory 24th

Hoare Logics for Time Bounds A Study in Meta Theory

引用

24th International Conference on Tools and algorithms for the Construction and analysis of Systems (TACAS) Held as Part of the 21st European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Haslbeck, Maximilian P. L. Nipkow, Tobias Tech Univ Munich Munich Germany

ISBN: (纸本)9783319899602;9783319899596

We study three different Hoare logics for reasoning about time bounds of imperative programs and formalize them in Isabelle/HOL: a classical Hoare like logic due to Nielson, a logic with potentials due to Carbonneaux et al. and a separation logic following work by Atkey, Chaguerand and Pottier. These logics are formally shown to be sound and complete. Verification condition generators are developed and are shown sound and complete too. We also consider variants of the systems where we abstract from multiplicative constants in the running time bounds, thus supporting a big-O style of reasoning. Finally we compare the expressive power of the three systems.

关键词： Hoare logic algorithm analysis Program verification

来源：评论

学校读者我要写书评

暂无评论

Characterization of Developmental Immature Fiber (im) Mutant and Texas Marker-I (TM-I) Cotton Fibers Using Attenuated Total Reflection Fourier Transform Infrared (ATR FT-IR) Spectroscopy

引用

APPLIED SPECTROSCOPY 2017年第7期71卷 1689-1695页

作者： Liu, Yongliang Kim, Hee-Jin ARS USDA Cotton Struct & Qual Res Unit SRRC New Orleans LA 70124 USA ARS USDA Cotton Fiber Biosci Res Unit SRRC New Orleans LA 70124 USA

The immature fiber (im) mutant is one type of cotton fiber mutant with unique characteristics of non-fluffy cotton bolls. Compared to its near-isogenic wild type Texas Marker-I (TM-I), im fiber has a thin secondary cell wall and is less mature. In this work, we applied the previously proposed principal component analysis (PCA) and simple algorithms to analyze the attenuated total reflection Fourier transform infrared (ATR FT-IR) spectra of developmental im and TM-I fibers. The results from these approaches could not effectively and consistently indicate the inherent difference between TM-I and im fibers at the same developmental stage. The difference between TM- I and corresponding im fibers was detected when comparing the normalized intensity variations of the 730 cm(-1) bands. The 730 cm(-1) band intensities in developmental im fibers are temporally lower than those in developmental TM-I fibers although they became similar when the TM-I and im fibers are fully mature. The observation might imply the likelihood of temporal reduction of amorphous regions in developmental im fibers rather than in developmental TM-I fibers.

关键词： Fourier transform infrared spectroscopy FT-IR attenuated total reflection ATR cellulose im mutant fiber secondary wall biosynthesis principal component analysis algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

An abstract model for branching and its application to mixed integer programming (vol 166, pg 369, 2017)

引用

MATHEMATICAL PROGRAMMING 2017年第1-2期166卷 407-407页

作者： Le Bodic, Pierre Nemhauser, George Monash Univ Fac Informat Technol Clayton Vic Australia Georgia Inst Technol Atlanta GA 30332 USA

The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a \(5\%\) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.

关键词： Branch and bound Abstract model Mixed integer programming Computational complexity algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Evaluating the quality of online optimization algorithms by discrete event simulation

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2017年第4期25卷 831-858页

作者： Dunke, Fabian Nickel, Stefan Karlsruhe Inst Technol Inst Operat Res Discrete Optimizat & Logist Kaiserstr 12 D-76131 Karlsruhe Germany

A key feature of dynamic problems which offer degrees of freedom to the decision maker is the necessity for a goal-oriented decision making routine which is employed every time the logic of the system requires a decision. In this paper, we look at optimization procedures which appear as subroutines in dynamic problems and show how discrete event simulation can be used to assess the quality of algorithms: after establishing a general link between online optimization and discrete event systems, we address performance measurement in dynamic settings and derive a corresponding tool kit. We then analyze several control strategies using the methodologies discussed previously in two real world examples of discrete event simulation models: a manual order picking system and a pickup and delivery service.

关键词： Online optimization algorithm analysis Discrete event simulation Order picking Pickup and delivery

来源：评论

学校读者我要写书评

暂无评论

Efficient Monte Carlo clustering in subspaces

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2017年第3期52卷 751-772页

作者： Olson, Clark F. Hunn, David C. Lyons, Henry J. Univ Washington Sch Sci Technol Engn & Math Bothell WA 98011 USA Microsoft Corp Redmond WA 98052 USA

Clustering of high-dimensional data is an important problem in many application areas, including image classification, genetic analysis, and collaborative filtering. However, it is common for clusters to form in different subsets of the dimensions. We present a randomized algorithm for subspace and projected clustering that is both simple and efficient. The complexity of the algorithm is linear in the number of data points and low-order polynomial in the number of dimensions. We present the results of a thorough evaluation of the algorithm using the OpenSubspace framework. Our algorithm outperforms competing subspace and projected clustering algorithms on both synthetic and real-world data sets.

关键词： Subspace clustering Projected clustering Monte Carlo algorithm algorithm analysis Classification

来源：评论

学校读者我要写书评

暂无评论

TraX: The visual Tracking eXchange protocol and library

引用

NEUROCOMPUTING 2017年 260卷 5-8页

作者： Cehovin, Luka Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 SI-1000 Ljubljana Slovenia

In this paper we address the problem of developing on-line visual tracking algorithms. We present a specialized communication protocol that serves as a bridge between a tracker implementation and utilizing application. It decouples development of algorithms and application, encouraging re-usability. The primary use case is algorithm evaluation where the protocol facilitates more complex evaluation scenarios that are used nowadays thus pushing forward the field of visual tracking. We present a reference implementation of the protocol that makes it easy to use in several popular programming languages and discuss where the protocol is already used and some usage scenarios that we envision for the future. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Computer vision Visual tracking Performance evaluation algorithm analysis Communication protocol Software library

来源：评论

学校读者我要写书评

暂无评论

On the maximum computing time of the bisection method for real root isolation

引用

JOURNAL OF SYMBOLIC COMPUTATION 2017年第Part2期79卷 444-456页

作者： Collins, George E.

The bisection method for polynomial real root isolation was introduced by Collins and Akritas in 1976. In 1981 Mignotte introduced the polynomials A(a,n)(x)=x(n) 2(ax - 1)(2), a an integer, a >= 2 and n >= 3. First we prove that if a is odd then the computing time of the bisection method when applied to A(a,n) dominates n(5)(log d)(2) where d is the maximum norm of A(a,n). Then we prove that if A is any polynomial of degree n with maximum norm d then the computing time of the bisection method, with a minor improvement regarding homothetic transformations, is dominated by n(5)(log d)(2). It follows that the maximum computing time of the bisection method is codominant with n(5)(log d)(2). (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Polynomial roots Real roots Root isolation Computing time algorithm analysis Dominance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：