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

Modelling the dynamics of stochastic local search on k-SAT

JOURNAL OF HEURISTICS 2007年第6期13卷 587-639页

作者： Fournier, Nicolas G. EPO Munich Germany

A new analytical tool is presented to provide a better understanding of the search space of k-SAT. This tool, termed the local value distribution, describes the probability of finding assignments of any value q' in the neighbourhood of assignments of value q. The local value distribution is then used to define a Markov model to model the dynamics of a corresponding stochastic local search algorithm for k-SAT. The model is evaluated by comparing the predicted algorithm dynamics to experimental results. In most cases the fit of the model to the experimental results is very good, but limitations are also recognised.

关键词： algorithm analysis experimental evaluation stochastic algorithms local search k-SAT

来源：评论

学校读者我要写书评

暂无评论

Mind the gap: A study of Tube tour

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第11期39卷 2705-2714页

作者： Drozdowski, M. Kowalski, D. Mizgajski, J. Mokwa, D. Pawlak, G. Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland

The problem considered in this paper can be expressed as a question: Is it possible to visit all Tube lines in a day? This is a new type of combinatorial optimization problem which generalizes classic problems like TSP, set cover. It has similarities with classic combinatorial optimization problems and ties with operations research applications. We call the graphs corresponding to the city railway systems subway graphs. Examples and properties of such graphs are described in the paper. We show that our problem is NP-hard. algorithms solving the problem are proposed and their performance is studied both analytically and experimentally on transportation networks of several big cities of the world. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Graph cycles Urban railway algorithm analysis Heuristics

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for learning sparse parities in the presence of noise

引用

THEORETICAL COMPUTER SCIENCE 2021年 873卷 76-86页

作者： Yan, Di Yu, Yu Liu, Hanlin Zhao, Shuoyao Zhang, Jiang Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

We revisit the Learning Sparse Parities with Noise (LSPN) problem on k out of n variables for k << n, and present the following findings. 1. For true parity size k = n(u) for any 0 < u < 1, and noise rate eta < 1/2, the first algorithm solves the (n,k,eta)-LSPN problem with constant probability and time/sample complexity n((1-u+o(1))k)/(1/2-eta)(2). 2. For any 1/2 < c(1) < 1, k = o(eta n/logn), and eta <= n (-c1)/4, our second algorithm solves the (n,k,eta)-LSPN problem with constant probability and time/sample complexity n(2(1-c1+o(1))k). 3. We show a "win-win" result about reducing the number of samples. If there is an algorithm that solves (n, k, eta)-LSPN problem with probability Omega(1), time/sample complexity n(O(k)) for k = o(n(1-c)), any noise rate eta = n(1-2C)/3 and 1/2 <= c < 1. Then, either there exists an algorithm that solves the (n, k, mu)-LSPN problem under lower noise rate mu = n(-c)/3 using only 2n samples, or there exists an algorithm that solves the (n, k ', mu)-LSPN problem for a much larger k ' = n(1-c) with probability n(-O(k))/poly(n), and time complexity poly(n) center dot n(O(k)), using only n samples. Our algorithms are simple in concept by combining a few basic techniques such as majority voting, reduction from the LSPN problem to its decisional variant, Goldreich-Levin list decoding, and computational sample amplification. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Learning theory algorithm analysis Learning parity with noise Learning sparse parity with noise Sample amplification

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING TASKS WITH AND/OR PRECEDENCE CONSTRAINTS

引用

SIAM JOURNAL ON COMPUTING 1995年第4期24卷 797-810页

作者： GILLIES, DW LIU, JWS UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of their predecessors is complete. These tasks are known as OR tasks. We analyze the complexity of two types of real-time AND/OR task scheduling problems. In the first type of problem, all the predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. We show that most problems involving tasks with individual deadlines are NP-complete, and then present two priority-driven heuristic algorithms to minimize completion time on a multiprocessor. These algorithms provide the same level of worst-case performance as some previous priority-driven algorithms for scheduling AND-only task systems.

关键词： NONPREEMPTIVE SCHEDULING LIST SCHEDULING MINIMAL LENGTH SCHEDULES algorithm analysis MULTIPROCESSOR SYSTEMS NP-COMPLETE PROBLEMS IMPRECISE COMPUTATION

来源：评论

学校读者我要写书评

暂无评论

Continued fraction real root isolation using the Hong root bound

引用

JOURNAL OF SYMBOLIC COMPUTATION 2016年 72卷 21-54页

作者： Collins, George E.

An investigation of the codominance maximum computing time of the continued fractions method (CF) for isolation of the real roots of a squarefree integral polynomial when applied to the two-parameter family of polynomials A(a,n) (x) = x(n) - 2(ax(2) - (a + 2)x + 1)(2), with n >= 5 and a >= 1. These polynomials have two roots, r(1) and r(2), in the interval (0, 1), with vertical bar r(1) - r(2)vertical bar < a(-n). It is proved that for these polynomials the maximum time required by CF to isolate those two close roots would be codominant with n(5)(Ina)(2) even if an "ideal" root bound were available and either the Homer method or the Budan method is used for translations. It is proved that if a power-of-two Hong root bound is used by CF to determine translation amounts then the time required to isolate the two close roots is dominated by n(6)(Ina) if a multiplication-free Budan translation method is used. Computations reveal that the Hong root bound is surprisingly effective when applied to the transformed polynomials that arise, engendering a minimum efficiency conjecture. It is proved that if the conjecture is true then the time to isolate the two close roots is dominated by n(5)(lna)(2). There is also evidence for a maximum efficiency conjecture. The two conjectures together, if true, make it likely that this time is codominant with n(5)(Ina)(2). (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Polynomial roots Real roots Root isolation Continued fractions Maximum computing time Root bounds Dominance algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Chemical Discrimination of Benzene Series and Molecular Recognition of the Sensing Process over Ti-Doped Co3O4

引用

ACS SENSORS 2022年第6期7卷 1757-1765页

作者： Cao, Zhengmao Ge, Yingzhu Wang, Wu Sheng, Jianping Zhang, Zijian Li, Jieyuan Sun, Yanjuan Dong, Fan Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci Res Ctr Environm & Energy Catalysis Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Sch Resources & Environm Chengdu 611731 Peoples R China

This work achieved the chemical discrimination of benzene series (toluene, xylene isomers, and ethylbenzene gases) based on the Ti-doped Co3O4 sensor. Benzene series gases presented different gas-response features due to the differences in redox rate on the surface of the Ti-doped Co3O4 sensor, which created an opportunity to discriminate benzene series via the algorithm analysis. Excellent groupings were obtained via the principal component analysis. High prediction accuracies were acquired via k-nearest neighbors, linear discrimination analysis (LDA), and support vector machine classifiers. With the confusion matrix for the data set using the LDA classifier, the benzene series have been well classified with 100% accuracy. Furthermore, in situ diffuse reflectance infrared Fourier transform spectroscopy (DRIFTS) and density functional theory calculations were conducted to investigate the molecular gas-solid interfacial sensing mechanism. Ti-doped Co3O4 showed strong Lewis acid sites and adsorption capability toward reaction species, which benefited the toluene gas-sensing reaction and resulted in the highly boosted gas-sensing performance. Our research proposed a facile distinction methodology to recognize similar gases and provided new insights into the recognition of gas-solid interfacial sensing mechanisms.

关键词： xylene isomers algorithm analysis Ti-doped Co3O4 in situ DRIFTS sensing mechanism

来源：评论

学校读者我要写书评

暂无评论

A survey of approximately optimal solutions to some covering and packing problems

引用

ACM COMPUTING SURVEYS 1997年第2期29卷 171-209页

作者： Paschos, VT Lamsade Université Paris-Dauphine

We survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex covering, the maximum set packing, and maximum independent set problems;we discuss their approximation performance and their complexity. For already known results, any time we have conceived simpler proofs than those already published, we give these proofs, and, for the rest, we cite the simpler published ones. Finally, we discuss how one can relate the approximability behavior (from both a positive and a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems.

关键词： algorithm analysis approximation algorithms combinatorial algorithms constrained optimization problem complexity

来源：评论

学校读者我要写书评

暂无评论

A new approach to on-demand loop-free routing in networks using sequence numbers

引用

COMPUTER NETWORKS 2006年第10期50卷 1599-1615页

作者： Garcia-Luna-Aceves, J. J. Mosko, Marc Perkins, Charles E. Univ Calif Santa Cruz Jack Baskin Sch Engn Santa Cruz CA 95062 USA Nokia Res Ctr Commun Syst Lab Mountain View CA 94043 USA

A new protocol is presented for on-demand, loop-free routing in ad hoc networks. The new protocol, called the labeled distance routing (LDR) protocol, uses a distance invariant to establish an ordering criterion and per-destination sequence numbers to reset the invariant resulting in loop-freedom at every instant. The distance invariant allows nodes to change their next hops or distances to destinations without creating routing-table loops. The destination sequence number, which only the destination may increment, permits nodes to reset the values of their distance invariants. The performance of LDR is compared against the performance of three other protocols that are representative of the state-of-the-art, namely AODV. DSR and OLSR;LDR's performance is shown to be far better than the other three protocols. (c) 2005 Elsevier B.V. All rights reserved.

关键词： routing protocol loop-free algorithm analysis ad hoc network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：