FD集最优覆盖多项式时间求解算法的研究

本文在详细分析了ＦＤ集的最小覆盖和最优覆盖的结构特性基础上，提出并讨论了一个最小覆盖成为最优覆盖的条件及一个最优覆盖珠属性集构成的特点，相应的引理和定理。最后给出一个求ＦＤ集最优覆盖的多项式时间算法。     

基于蜂窝结构的传感器网络覆盖问题求解算法

在无线传感器网络中,求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时,目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.     

WSN中有效的最小单位圆集覆盖算法*

针对具有不同传输半径的无线传感器网络覆盖与广播数据转发问题,提出了一种以最小单位圆覆盖集作为广播数据转发集的算法。该算法能有效计算出覆盖范围的轮廓集,具有最优的时间复杂度O(n log n)。对每个节点,该算法以其最少数量的邻居节点子集实现所有邻居节点的覆盖,并证明了该算法找到的最小单位圆覆盖集与其轮廓集是相等的。详细的仿真实验及与现有算法的比较表明,提出的覆盖算法不仅以最少数量的节点实现了网络覆盖与广播数据转发,同时延长了网络生命期。     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

LR最小替换集求解算法研究

文中对Ｄ．Ｍａｉｅｒ提出的关于关系数据库中的ＬＲ最小集的结构进行了分析，提出了一个比“ＬＲ最小集”更为简化的ＦＤ集的覆盖－ＬＲ最小替换集。给出了一个求ＬＲ最小替换集的多项式时间算法。修正了Ｄ．Ｍａｉｅｒ在其文中给出的一个ＦＤ集为最优覆盖的必要条件。     

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.     

An Optimal Algorithm for the Minimum Disc Cover Problem

The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general α-hull problem. In spite of being a special case, the disc cover problem is not easier than the general α-hull problem. In addition to applying the existing α-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the α-hull approach would fail.     

A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs

A memetic approach that combines a genetic algorithm (GA) and quadratic programming is used to address the problem of optimal portfolio selection with cardinality constraints and piecewise linear transaction costs. The framework used is an extension of the standard Markowitz mean–variance model that incorporates realistic constraints, such as upper and lower bounds for investment in individual assets and/or groups of assets, and minimum trading restrictions. The inclusion of constraints that limit the number of assets in the final portfolio and piecewise linear transaction costs transforms the selection of optimal portfolios into a mixed-integer quadratic problem, which cannot be solved by standard optimization techniques. We propose to use a genetic algorithm in which the candidate portfolios are encoded using a set representation to handle the combinatorial aspect of the optimization problem. Besides specifying which assets are included in the portfolio, this representation includes attributes that encode the trading operation (sell/hold/buy) performed when the portfolio is rebalanced. The results of this hybrid method are benchmarked against a range of investment strategies (passive management, the equally weighted portfolio, the minimum variance portfolio, optimal portfolios without cardinality constraints, ignoring transaction costs or obtained with L₁ regularization) using publicly available data. The transaction costs and the cardinality constraints provide regularization mechanisms that generally improve the out-of-sample performance of the selected portfolios.     

一种求解平面图的最小顶点覆盖算法

最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。     

On mapping processes to processors in distributed systems

This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. Anoptimal path cover of a simple graphG is a set of vertex-disjoint paths that cover all the vertices ofG and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.A preliminary version of this paper was presented at the 6th IEEE Conference on Computer Communications (INFOCOM '87).This reseach is supported in part by National Semiconductor (Israel), Ltd.     

最小一致性覆盖在不完备规则集中的应用

将Martin Ester提出的最小一致性覆盖方法应用于不完备规则集的规则提取。首先对不完备数据分别进行两种方法的预处理,然后通过定义数据间的一致性来使规则提取的覆盖问题转化成划分问题。经过UCI上两个数据集的测试,证明了这种方法的有效性。     

一种混合化学反应优化算法求解最小顶点覆盖问题

最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。论文针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学化反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。     

用关键特征集对逻辑进行优化

提出了一个两级逻辑优化的新算法，与通过函数质蕴涵集求解覆盖的传统算法不同，文中将求解逻辑函数的质蕴涵项与推导覆盖问题相结合，直接得出覆盖问题的解。算法的主要问题可以简化为：对于立方描述的单元，求解最小覆盖，在这个过程中又提出了一种改进的覆盖吸收算法，基于关键特征集合的选拔吸收算法，此算法不用求所有的立方，通过标准的测试例子与原来的Espresso算法作比较，对于大电路，在计算时间上，新算法有明显的改进。     

关于标准FD集的几个相关问题的讨论

本文为讨论ＦＤ集的简化和研究最优覆盖的多项式求法，对标准ＦＤ集进行了定义和讨论。同时，还定义了与它相关的几个概念，讨论了标准ＦＤ集Ｆ成为最小覆盖的充要条件及其它问题。     

Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks

A minimum connected dominating set (MCDS) is used as virtual backbone for efficient routing and broadcasting in ad hoc sensor networks. The minimum CDS problem is NP-complete even in unit disk graphs. Many heuristics-based distributed approximation algorithms for MCDS problems are reported and the best known performance ratio has (4.8+ln 5). We propose a new heuristic called collaborative cover using two principles: 1) domatic number of a connected graph is at least two and 2) optimal substructure defined as subset of independent dominator preferably with a common connector. We obtain a partial Steiner tree during the construction of the independent set (dominators). A final postprocessing step identifies the Steiner nodes in the formation of Steiner tree for the independent set of G. We show that our collaborative cover heuristics are better than degree-based heuristics in identifying independent set and Steiner tree. While our distributed approximation CDS algorithm achieves the performance ratio of (4.8+ln 5){rm opt} + 1.2, where {rm opt} is the size of any optimal CDS, we also show that the collaborative cover heuristic is able to give a marginally better bound when the distribution of sensor nodes is uniform permitting identification of the optimal substructures. We show that the message complexity of our algorithm is O(nDelta^{2} ), Delta being the maximum degree of a node in graph and the time complexity is O(n).     

Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the k given sets. Such a partition defines a probability distribution, obtained by dividing each part size by n. The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat =log ₂ e bits ≃1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem. G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).     

Nonlinear filtering for discrete-time linear systems withnon-Gaussian initial data

The optimal minimum mean-square error filtering problem is discussed for a linear system with non-Gaussian initial distribution. An input/output realization is derived using an absolutely continuous change of probability measure. A representation result is presented which facilitates the derivation of optimal filter realization     

Using an interval graph approach to efficiently solve the housing benefit data retrieval problem

Rappos and Thompson use a set covering formulation and a commercial software package to solve the problem of trying to minimize the number of data sets that have to be read in retrieving all new housing benefit (HB) data entries for a fixed period of time. In this paper, we show that determining the minimum number of data sets that have to be read in retrieving all new HB data entries for a fixed period of time can be solved by finding a minimum size clique cover for an interval graph. Since it is well‐known that a greedy algorithm finds a guaranteed minimum size clique cover for an interval graph, this approach will be more efficient than a set covering approach. Finally, it is obvious that this interval graph formulation and greedy algorithm solution approach is applicable to other data retrieval problems.     

Molecular solutions for minimum and exact cover problems in the tile assembly model

The tile assembly model is a novel biological computing model where information is encoded in DNA tiles. It is an efficient way to solve NP-complete problems due to its scalability and parallelism. In this paper, we apply the tile assembly model to solve the minimum and exact set cover problems, which are well-known NP-complete problems. To solve the minimum set cover problem, we design a MinSetCover system composed of three parts, i.e., the seed configuration subsystem, the nondeterministic choice subsystem, and the detection subsystem. Moreover, we improve the MinSetCover system and propose a MinExactSetCover system for solving the problem of exact cover by 3-sets. Finally we analyze the computation complexity and perform a simulation experiment to verify the effectiveness and correctness of the proposed systems.