Parallel and serial heuristics for the minimum set cover problem

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.Research of both authors was supported by NSF Grant No. MIP-8807540.     

A note on ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’

A flaw in the greedy approximation algorithm proposed by Zhang et al. (2009) [1] for the minimum connected set cover problem is corrected, and a stronger result on the approximation ratio of the modified greedy algorithm is established. The results are now consistent with the existing results on the connected dominating set problem which is a special case of the minimum connected set cover problem.     

基于模拟植物生长算法的求解MCCS问题的研究

为了降低耗能和减少花费,提出了对无线传感网络设计中的最小连通集合划分的方法.采用对网络进行Voronoi划分成近似覆盖集合,对不满足连通的情况采用一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通的方法.通过对算法的时间复杂度分析及算例实验,验证了该算法不但可获得最优解,同时精度和性能也有提高,明显优于其它方法.     

Guarding a set of line segments in the plane

We consider the following problem: Given a finite set of straight line segments in the plane, find a set of points of minimum size, so that every segment contains at least one point in the set. This problem can be interpreted as looking for a minimum number of locations of policemen, guards, cameras or other sensors, that can observe a network of streets, corridors, tunnels, tubes, etc. We show that the problem is strongly NP-complete even for a set of segments with a cubic graph structure, but in P for tree structures.     

Discovering a cover set of ARsi with hierarchy from quantitative databases

This paper extends the work on discovering fuzzy association rules with degrees of support and implication (ARsi). The effort is twofold: one is to discover ARsi with hierarchy so as to express more semantics due to the fact that hierarchical relationships usually exist among fuzzy sets associated with the attribute concerned; the other is to generate a “core” set of rules, namely the rule cover set, that are of more interest in a sense that all other rules could be derived by the cover set. Corresponding algorithms for ARsi with hierarchy and the cover set are proposed along with pruning strategies incorporated to improve the computational efficiency. Some data experiments are conducted as well to show the effectiveness of the approach.     

基于覆盖粗糙集模型的层次聚类算法

目前大部分聚类算法只适用于处理属性取值为单值的数值型数据,介绍了一种新的基于粗糙集理论的聚类算法,该算法不仅可用于取值为单值的数值型数据聚类,而且能够用于取值为多值的非数值型数据聚类.该算法利用基于相容关系的属性最小覆盖来求解对象各属性的对象属性信息粒.在此基础上,通过对象属性信息粒和对象粗糙相似度的运算构建各对象的相容粒.最后,把具有相同相容粒的对象视为同一等价类,从而实现对论域的聚类,进而对数据对象进行层次聚类.实验结果表明,该算法是可行的.     

The vectorization of the partition problem

This paper describes a vectorized algorithm for the partition problem, a famous NP-complete problem. A set of partition problems that required 518 seconds to be solved on a VAX/8550 computer would require only 2 seconds on the Cyber 205 under the vector mode. A partition problem with n equal to 1000 was solved in only 6.34 seconds.     

MSC问题的一类表面DNA解法

利用基于表面的DNA粘贴模型求解最小集合覆盖问题。改进体现在计算模版表面穷举了所有可能的结果,同一时间验证结果是否满足条件,真正实现了DNA的强大并行性。同时在互补的寡聚核苷酸片段发生退火反应时,利用特殊的化学反应,通过催化剂来决定是否杂交,减少了人工参与,提高了计算效率。通过计算机仿真模拟验证了模型的可行性。     

A genetic algorithm for the minimum generating set problem

Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinatorial number theory and is related to some real-world problems, such as planning radiation therapies.We present a new formulation to this problem (based on the terminology for the multiple knapsack problem) that is used to design an evolutionary approach whose performance is driven by three search strategies; a novel random greedy heuristic scheme that is employed to construct initial solutions, a specialized crossover operator inspired by real-parameter crossovers and a restart mechanism that is incorporated to avoid premature convergence. Computational results for problem instances involving up to 100,000 elements show that our innovative genetic algorithm is a very attractive alternative to the existing approaches.     

The problem of determining the size of a complete set of reductions

This article is the tenth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for accurately predicting the size of a complete set of reductions when such a set exists. We include a suggestion for evaluating a proposed solution to this research problem.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 problem of guaranteeing the existence of a complete set of reductions

This article is the eleventh of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for guaranteeing the existence of a complete set of reductions. We include a suggestion for evaluating a proposed solution to this research problem.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 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.     

The problem of guaranteeing the absence of a complete set of reductions

This article is the twelfth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for guaranteeing the absence of a complete set of reductions. We include a suggestion for evaluating a proposed solution to this research problem.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.     

An iterative algorithm based on level set method for the shape recovery problem

In this paper, we propose an iterative algorithm based on the level set method for the shape recovery problem. We use a suitable preconditioner for the artificial time-dependent system for the level set formulation and propose an iterative algorithm of the level set function. We prove the convergence of our algorithm under some hypothesis. Numerical experiments show the efficiency of the algorithm.     

A priori optimization for the probabilistic maximum independent set problem

We first propose a formal definition for the concept of probabilistic combinatorial optimization problem (under the a priori method). Next, we study the complexity of optimally solving probabilistic maximum independent set problem under several a priori optimization strategies as well as the complexity of approximating optimal solutions. For the different strategies studied, we present results about the restriction of probabilistic independent set on bipartite graphs.     

基于遗传算法的集合划分问题求解

集合划分问题是组合优化领域中有着广泛应用基础的著名问题,属于NP难问题.通过引入精英策略提出对遗传算法的改进,并为了能把遗传算法应用到集合划分问题,对数学模型进行了等价变换.针对集合划分问题,设计出一种高效的基因表示,避免了组合优化中处理约束条件的麻烦.解决了传统二进制基因编码无法精确适应离散优化问题,首次提出一种离散编码解决方案.最后,使用Visual C 6编程实现,取得较好的结果.     

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.