Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。

Gravity-based heuristic for set covering problems and its application in fault diagnosis

A novel algorithm named randomized binary gravita- tional search （RBGS） algorithm is proposed for the set covering problem （SCP）. It differs from previous SCP approaches because it does not work directly on the SCP matrix. In the proposed algo- rithm, the solution of SCP is viewed as multi-dimension position of objects in the binary search space. All objects in the space attract each other by the gravity force, and this force causes a global movement of all objects towards the objects with heavier masses which correspond to good solutions. Computation results show that the proposed algorithm is very competitive. In addition, the proposed aigodthm is extended for SCP to solve the fault diagno- sis problem in graph-based systems.

Efficient Cover Set Selection in Wireless Sensor Networks

到大程度，一个基于簇的分布式的传感器网络的有效性取决于传感器节点提供的范围。在任何特别时刻激活仅仅传感器节点的必要数字是节省全面精力的一个有效方法。然而，因为无线传感器网络的高密度的推广，这是一个 NP 完全的问题。在这份报纸，基于改进 NSGA-II (排序基因算法的优秀人材 nondominated ) 寻找算法的一篇小说被建议选择一个最佳的盖子集合。与在以前的工作使用的二进制察觉模型相对照，一个概率的察觉模特儿与察觉错误范围和范围阀值在联合被收养。与被保证的完整的网络范围，很多个节点被转变为休眠模式节省精力。传播联合并且删除操作员被建议提高搜索能力。广泛的模拟结果被介绍表明我们的途径的有效性。

Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Currently,the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus,a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem,we are interested in testing the performance of the Fruit Fly Algorithm,this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces,based on the foraging behavior of the fruit fly,which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach,because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

Covering-Based Soft Rough Sets

Covering-based rough sets process data organized by a covering of the universe. A soft set is a parameterized family of subsets of the universe. Both theories can deal with the uncertainties of data. Soft sets have not any restrictions on the approximate description of the object,and they might form a covering of the universe. From this viewpoint,we establish a connection between these two theories. Specifically,we propose a complementary parameter for this purpose. With this parameter,the soft covering approximation space is established and the two theories are bridged. Furthermore,we study some relations between the covering and the soft covering approximation space and obtain some significant results. Finally,we define a notion of combine parameter which can help us to simplify the set of parameters and reduce the storage requirement of a soft covering approximation space.

Study on covering rough sets with topological methods

The authors study the covering rough sets by topological methods. They combine the covering rough sets and topological spaces by means of defining some new types of spaces called covering rough topological (CRT) spaces based on neighbourhoods or complementary neighbourhoods. As the separation axioms play a fundamental role in general topology, they introduce all these axioms into covering rough set theories and thoroughly study the equivalent conditions for every separation axiom in several CRT spaces. They also investigate the relationships between the separation axioms in these special spaces and reveal these relationships through diagrams in different CRT spaces.

Properties and Relations of Several Operators Based on Covering Rough Sets

The coveting rough sets theory is a generalization of traditional rough set theory, and can also describe information with incompleteness and fuzziness in information systems. In this paper, we first provide the definitions of several upper and lower covering approximation operators on the covering approximation space. Then, we study the properties of these operators. Finally, we propose the mutual relations between approximation operators and similar relations of the operator （ I ） based on the covering rough sets.

Numerical Characterizations of Covering Rough Sets Based on Evidence Theory

Covering rough sets are improvements of traditional rough sets by considering cover of universe instead of partition.In this paper,we develop several measures based on evidence theory to characterize covering rough sets.First,we present belief and plausibility functions in covering information systems and study their properties.With these measures we characterize lower and upper approximation operators and attribute reductions in covering information systems and decision systems respectively.With these discussions we propose a basic framework of numerical characterizations of covering rough sets.

Set (k, n)-Exactly covering problem

With the （ k, n ）-threshold scheme of secret sharing in the field of information security technology as an application background, the concept of set （ k, n ）-exact cover is presented in this paper. It is a modification of the original concept of set covering problem. It is also different from the concept of exact cover defined by J.E. Hopcmft. Some properties of （k, n ） -exact cover are investigated; a sufficient condition for a set to be （ k, n ） -exactly coverable is given. It follows that a feasible assignment scheme of a set for the （ k, n） -exact eover is obtained if this set satisfies the sufficient condition.

A NEGATIVE ANSWER TO A CONJECTURE ON SELF-SIMILAR SETS WITH OPEN SET CONDITION

Zhou and Feng posed a conjecture on self-similar set in 2004. In this paper, a self-similar set is constructed which has a best covering but its natural covering is not a best one. Thus, we indeed give a negative answer to the conjecture.

AN ANSWER TO A CONJECTURE ON SELF-SIMILAR SETS

In this paper, we construct a self-similar set which has a best covering but it is not the natural covering, thus negate the conjecture on self-similar sets posed by Z. Zhou in 2004.

基于Cover级别的中文信息检索技术的研究

信息检索系统如果能较精确地定位于文章中用户关心的部分必将提高用户的检索效率。基于Cover级别的检索策略就是针对上述问题提出的。基于Cover级别的检索策略以用户查询的关键词集合作为输入,在被检索文档中找到包含关键词集合的最短文本片断集作为输出。文章采用了一种经过改进的基于Cover级别的检索策略,对系统返回的文本片断作了限制,并在检索过程中使用了贪心算法(Greedy Algorithm)的思想,最后将其应用到中文信息检索系统中。实验证明,采用改进的策略比原有的基于Cover级别的检索策略在返回有效结果个数和平均排序倒数(MRR)等指标上都有了提高。

Dualities in Covering Rough Operations

Rough set theory is a technique of granular computing. In this paper, we study a type of generalized rough sets based on covering. There are several literatures[1,40-43] exploring covering-based rough sets. Our focus of this paper is on the dualities in rough operations.

函数空间C_k(X)上的T-Tightness和Set-Tightness

讨论了函数空间Ck(X)在赋予紧开拓扑下的T-tightness和set-tightness性质,利用开k覆盖获得了Ck(X)是T-tightness空间和set-tightness空间的两个对偶定理,将点态收敛拓扑函数空间Cp(X)的相关结论推广到紧开拓扑函数空间Ck(X)上.

动态图上基于2-HOP COVER的TOP-K最短路径算法

top-k最短路径问题是在给定图中查找两个节点的最短的k条路径的问题。对于大规模的图,这一问题的算法通常分为两个步骤:耗时的一次性预处理和快速的查询应答。但是,很多这样的算法都是针对静态图的。如果图进行了改变,耗时的预处理就要重做。基于静态图中的2-hop cover的top-k最短路径算法,提出一个适用于动态的有向带权图上的top-k最短路径算法,其创新部分是一个更新预处理数据的子程序。该算法只需要修改原始图的很小一部分索引集就可以得到更新后图的索引集,极大地减少了算法的总运行时间。证明了算法的正确性,并分析了算法的时间和空间复杂度。

Heat Setting Technology for the Glove of Flexible Medical Orthosis

In order to meet the curative effect,the glove of the flexible medical orthosis was designed to use nylon / spandex and polyester / spandex covered yarns to knit the glove by parts.For the purpose of confirming the best heat setting technology of the glove knitted by multicomponent materials, different heat setting technologies with different temperature and time were tested on the nylon / spandex and the polyester / spandex knitted fabrics.And the effects of the heat setting technology on dimensional stability and elastic recovery of the two kinds of fabrics were analyzed as well.The results show that in the proper range of temperature and time,dimensional stability and elastic recovery of the nylon / spandex knitted fabric become better with the increases of temperature and time.And dimensional stability of the polyester / spandex knitted fabric also turns good.But its elastic recovery doesn't change obviously.All the measured values were compared with each other.And the results indicate that dimensional stability and elastic recovery of these two kinds of fabrics both are great after the heat setting technology of temperature 180 ℃ and time 60 s.

THE EXACT MEASURES OF A CLASS OF SELF-SIMILAR SETS ON THE PLANE

Let S belong to R^2 be the attractor of the iterated function system {f1, f2, f3 } iterating on the unit equilateral triangle So. where fi（x） =λix ＋ bi, i = 1,2, 3, x =（x1, x2）, b1=（0, 0）, b3=（1-λ3 /2,√3/2 （1-λ3）） This paper determines the exact Hausdorff measure, centred covering measure and packing measure of S under some conditions relating to the contraction parameter.

NOTE ON THE PAPER “ AN NEGATIVE ANSWER TO A CONJECTURE ON THE SELF-SIMILAR SETS SATISFYING THE OPEN SET CONDITION”

In this paper, we present a more simple and much shorter proof for the main result in the paper ＂ An negative answer to a conjecture on the self-similar sets satisfy- ing the open set condition＂, which was published in the journal Analysis in Theory and Applications in 2009.

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

Minimum Covering RandićEnergy of a Graph

Randićenergy was first defined in the paper [1]. Using minimum covering set, we have introduced the minimum covering Randićenergy REC (G) of a graph G in this paper. This paper contains computation of minimum covering Randićenergies for some standard graphs like star graph, complete graph, thorn graph of complete graph, crown graph, complete bipartite graph, cocktail graph and friendship graphs. At the end of this paper, upper and lower bounds for minimum covering Randićenergy are also presented.