The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

Entropy of capacities on lattices and set systems

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

A set coverage problem

This paper shows that with B={1,2,…,n}, the smallest k such that

     

The solution set of the mixed ls-tls problem

Although the least squares (LS) problem and the total least squares (TLS) problem have received much attention, the mixed LS-TLS problem still remains to be investigated. In this paper, we study the necessary and sufficient solvability conditions for the mixed LS-TLS problem in Frobenius norm. The solution set, the minimum Frobenius norm solution and an algorithm to obtain the solution are also given. Further we propose the mixed LS-TLS problem in spectral norm and present the solvability condition.     

A generalized moment problem in vector lattices

We present a moment problem in the context of vector lattices. The corresponding generalized moment theorem and its corrolaries are stated and proved.     

Computational study on planar dominating set problem

Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with n vertices and dominating number k can be solved in time using tree/branch-decomposition based algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time and memory space for the class of graphs with small branchwidth. For the class of graphs with large branchwidth, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs.     

容差粗糙集卫星遥感数据分类

结合粗糙集理论和遥感数据中地物光谱特征空间分布信息,提出了一种基于光谱特征邻域的容差粗糙集分类方法,用来处理卫星遥感数据分类中的不确定性问题。利用北京地区Landsat-5 TM数据进行分类试验,对算法分类过程进行讨论及其分类结果进行验证分析;结果表明：文中方法在可理解性和稳定性上体现出比较好的性质,能够有效处理卫星遥感数据分类中存在的不确定性因素,在具有复杂光谱特征地物分类方面具有发展潜力。     

The problem of extending the set of support strategy

This article is the third of a series of articles discussing various open research problems in automated reasoning. The problem proposed for research focuses on redefining or extending the definition of the set of support strategy so that the resulting strategy is as effective at all clause levels as it is at level 1. We include specific test problems for evaluating a proposed solution to this research problem.     

The problem of self-analytically choosing the set of support

This article is the seventh of a series of articles discussing various open research problems in automated reasoning. Here we focus on self-analysis and the set of support strategy. The problem proposed for research asks for one to find a means for an automated reasoning program to self-analytically determine which clauses to be in the set of support at various points during the program's attempt to complete a given assignment. For evaluating a proposed solution to this research problem, we include suggestions concerning possible test problems.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contract W-31-109-Eng-38.     

The query clustering problem: a set partitioning approach

In this research, we address the query clustering problem which involves determining globally optimal execution strategies for a set of queries. The need to process a set of queries together often arises in deductive database systems, scientific database systems, large bibliographic retrieval systems and several other database applications. We address the optimization problem from the perspective of overlaps in data requirements, and model the batched operations using a set-partitioning approach. In this model, we first consider the case of m queries each involving a two-way join operation. We develop a recursive methodology to determine all the processing strategies in this case. Next, we establish certain dominance properties among the strategies, and develop exact as well as heuristic algorithms for selecting an appropriate strategy. We extend this analysis to a clustering approach, and outline a framework for optimizing multiway joins. The results show that the proposed approach is viable and efficient, and can easily be incorporated into the query processing component of most database systems     

Reduction method for concept lattices based on rough set theory and its application

Rough set theory and formal concept analysis are two complementary mathematical tools for data analysis. In this paper, we study the reduction of the concept lattices based on rough set theory and propose two kinds of reduction methods for the above concept lattices. First, we present the sufficient and necessary conditions for justifying whether an attribute and an object are dispensable or indispensable in the above concept lattices. Based on the above justifying conditions, we propose a kind of multi-step attribute reduction method and object reduction method for the concept lattices, respectively. Then, on the basis of the defined discernibility functions of the concept lattices, we propose a kind of single-step reduction method for the concept lattices. Additionally, the relations between the attribute reduction of the concept lattices in FCA and the attribute reduction of the information system in rough set theory are discussed in detail. At last, we apply the above multi-step attribute reduction method for the concept lattices based on rough set theory to the reduction of the redundant premises of the multiple rules used in the job shop scheduling problem. The numerical computational results show that the reduction method for the concept lattices is effective in the reduction of the multiple rules.     

Solving the set cover problem on a supercomputer

Supercomputers, such as CRAY-1, CRAY X-MP, CYBER 205, ETA10, … etc, have been regularly used for solving numerical problems. It is very rare that supercomputers are used to solve combinatorial problems. In this paper, we present an efficient vectorized algorithm to solve the set cover problem, which was proved to be NP-complete, on a supercomputer, ETA10-Q108. This algorithm fully utilizes vector instructions. Experiments are performed both on ETA10-Q108 and VAX/8550 for comparison. It takes VAX/8550 1174.5 seconds to solve a set of problem instances while it takes ETA10-Q108 only 26.6 seconds to solve the same set of problems. For a problem instance involving 7000 elements in a set, it takes 47.74 seconds for the supercomputer to solve it. If VAX/8550 is used, it will need roughly 15 hours. Thus we conclude that it is quite feasible to solve the set cover problem by using supercomputers.     

Maximum weight k-independent set problem on permutation graphs

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.     

集合覆盖问题的数据约简研究*

针对当前解决大规模集合覆盖问题的算法普遍存在着效率不高的问题,提出了一套削减数据规模的约简方法,并给出了一个能够与其他所有解决集合覆盖问题算法相结合的约简算法。用Beasley提出的45个测试用例进行试验,结果显示贪心算法和遗传算法在结合了约简算法后能够在更少的时间内得到更优的解,表明该约简方法和约简算法可以有效提高传统算法和智能算法解决大规模集合覆盖问题的效率。     

The problem of finding an inference rule for set theory

This article is the ninth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding an inference rule for set theory. The problem proposed for research asks one to find a means for building in set-theoretic reasoning in a manner similar to the way paramodulation builds in equality-oriented reasoning. For evaluating a proposed solution to this research problem, we include suggestions concerning possible test problems.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contract W-31-109-Eng-38.     

Maximal independent set graph partitions for representations of body-centered cubic lattices

A maximal independent set graph data structure for a body-centered cubic lattice is presented. Refinement and coarsening operations are defined in terms of set-operations resulting in robust and easy implementation compared to a quad-tree-based implementation. The graph only stores information corresponding to the leaves of a quad-tree thus has a smaller memory foot-print. The adjacency information in the graph relieves one from going up and down the quad-tree when searching for neighbors. This results in constant time complexities for refinement and coarsening operations.