一个关于求解k-种产品选址问题的近似算法

对于k-种产品工厂选址问题,有如下描述：存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。     

一类弱支配集问题的近似算法

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为Inn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

Problem representation for refinement

In this paper we attempt to develop a problem representation technique which enables the decomposition of a problem into subproblems such that their solution in sequence constitutes a strategy for solving the problem. An important issue here is that the subproblems generated should be easier than the main problem. We propose to represent a set of problem states by a statement which is true for all the members of the set. A statement itself is just a set of atomic statements which are binary predicates on state variables. Then, the statement representing the set of goal states can be partitioned into its subsets each of which becomes a subgoal of the resulting strategy. The techniques involved in partitioning a goal into its subgoals are presented with examples.     

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

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

Measure-controlled dynamic systems: Polyhedral approximation of their reachable set boundary

An algorithm for polyhedral approximation of the reachable set of impulsive dynamic control systems is designed. The boundary points of the reachable set are determined by recursively generating and solving a family of auxiliary optimal impulsive control problems with state-linear objective functional. The impulsive control problem is solved with an algorithm that implicitly reduces the problem an ordinary optimal control problem. The reduced problem thus obtained is solved with an algorithm based on local approximations of the reachable set.     

A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows

This paper presents a hybrid genetic algorithm to solve a multi-depot homogenous locomotive assignment problem with time windows. The locomotive assignment problem is to assign a set of homogeneous locomotives locating in a set of dispersed depots to a set of pre-schedules trains that are supposed to be serviced in pre-specified hard/soft time windows. A mathematical model is presented, using vehicle routing problem with time windows (VRPTW) for formulation of the problem. A cluster-first, route-second approach is used to inform the multi-depot locomotive assignment to a set of single depot problems and after that we solve each problem independently. Each single depot problem is solved heuristically by a hybrid genetic algorithm that in which Push Forward Insertion Heuristic (PFIH) is used to determine the initial solution and λ-interchange mechanism is used for neighborhood search and improving method. A medium sized numerical example with different scenarios is presented and examined to more clarification of the approach as well as to check capabilities of the model and algorithm. Also some of the results are compared with the solutions produced by branch & bound technique to determine validity and quality of the model. The experiments with a set of 15 completely random generated instance problems indicate that this algorithm is efficient and solves the problem in a polynomial time.     

基于规划的空间布局

本文基于正规集首先建立了一个空间布局问题的形式化定义,然后分析了这一问题的计算复杂度,并证明了基于网格上空间布局问题的可计算性.重点介绍了基于分布式规划的住宅平面布局问题的求解模型,同时给出了一个实例,最后分析了规划方法和分布式规划的一些优点.     

面向超图数据的最大独立集算法

超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出4种高效的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在10个真实超图数据集上进行实验, 结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.     

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.     

Disjoint pattern matching and implication in strings

We deal with the problem of deciding whether a given set of string patterns implies the presence of a fixed pattern. While checking whether a set of patterns occurs in a string is solvable in polynomial time, this implication problem is well known to be intractable. Here we consider a version of the problem when patterns in the set are required to be disjoint. We show that for such a version of the problem the situation is reversed: checking whether a set of patterns occurs in a string is NP-complete, but the implication problem is solvable in polynomial time.     

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

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

Visiting convex regions in a polygonal map

This paper is concerned with a variant of the multi-goal path planning in which goals are represented as convex polygons. The problem is to find a closed shortest path in a polygonal map such that all goals are visited. The proposed solution is based on a self-organizing map (SOM) algorithm for the traveling salesman problem. Neurons’ weights are considered as nodes inside the polygonal domain and connected nodes represent a path that evolves according to the proposed adaptation rules. In addition, a reference algorithm based on the solution of the traveling salesman problem and the consecutive touring polygons problem is provided to find high quality solutions of the created set of problems. The problems are designed to represent various inspection and patrolling tasks and can form a kind of benchmark set for multi-goal path planning algorithms. The performance of the algorithms is examined in this problem set, which includes an instance of the watchman route problem with restricted visibility range. The proposed SOM based algorithms provide a unified approach to solve various visibility based routing problems in polygonal maps while they provide a competitive quality of solutions to the reference algorithm with significantly lower computational requirements.     

A tabu search heuristic for the concentrator location problem

The concentrator location problem (CLP) is a classical problem in the network design literature. Given a set of candidate locations and the concentrator capacities, the problem is to answer the following related questions. How many concentrators should be used? Where should they be located? Which users are to be assigned to each concentrator? A Lagrangian relaxation is used to obtain lower bounds for this problem. The Lagrangian relaxation is complemented by a tabu search (TS) metaheuristic. Computational results are given for a set of randomly generated problems and for test problems available in the literature. The tabu search heuristic (TSH) is shown to be competitive with other solution procedures available for the problem.     

Optimal control of switching systems

This paper considers an optimal control problem for a switching system. For solving this problem we do not make any assumptions about the number of switches nor about the mode sequence, they are determined by the solution of the problem. The switching system is embedded into a larger family of systems and the optimization problem is formulated for the latter. It is shown that the set of trajectories of the switching system is dense in the set of trajectories of the embedded system. The relationship between the two sets of trajectories (1) motivates the shift of focus from the original problem to the more general one and (2) underlies the engineering relevance of the study of the second problem. Sufficient and necessary conditions for optimality are formulated for the second optimization problem. If they exist, bang-bang-type solutions of the embedded optimal control problem are solutions of the original problem. Otherwise, suboptimal solutions are obtained via the Chattering Lemma.     

Exact satisfiability,a natural extension of set partition,and its average case behavior

The problem of determining whether a Boolean formula in conjunctive normal form is satisfiable in such a way that in each clause exactly one literal is set true, and all the other literals are set false is called the exact satisfiability problem. The exact satisfiability problem is well known to be NP-complete [5] and it contains the well known set partitioning problem as a special case. We study here the average time complexity of a simple backtracking strategy for solving the exact satisfiability problem under two probability models, the constant density model and the constant degree model. For both models we present results sharply separating classes of instances solvable in low degree polynomial time in the average from classes for which superpolynomial or exponential time is needed in the average.     

Vertex covering by paths on trees with its applications in machine translation

Given a tree and a set of paths in the tree, the problem of finding a minimum number of paths from the given path set to cover all the vertices in the tree is investigated in the paper. To distinguish from the classical path cover problem, such an optimization problem is referred to as vertex covering by paths. The problem and its edge variant, edge covering by paths, find applications in machine translation. Complexity and algorithmic results are presented for the problem and its edge variant.     

Robust maximum principle for multi-model LQ-problem

This paper presents the version of the robust maximum principle in the context of multi-model control formulated as the minimax Bolza problem. The cost function contains a terminal term as well as an integral one. A fixed horizon and terminal set are considered. The necessary conditions of the optimality are derived for the class of uncertain systems given by an ordinary differential equation with parameters from a given finite set. This problem consists in the control design providing a good behaviour for a given class of multi-model system. It is shown that the design of the minimax optimal controller is reduced to a finite-dimensional optimization problem given at the corresponding simplex set containing the weight parameters to be found. The robust optimal control may be interpreted as a mixture (with the optimal weights) of the controls which are optimal for each fixed parameter value. The proof is based on the recent results obtained for minimax Mayer problem (Boltyanski and Poznyak 1999a). The minimax linear quadratic control problem is considered in detail and the illustrative examples dealing with finite as well as infinite horizons conclude this paper.     

A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

Heuristics for automated knowledge source integration and service composition

The NP-hard component set identification problem is a combinatorial problem arising in the context of knowledge discovery, information integration, and knowledge source/service composition. Considering a granular knowledge domain consisting of a large number of individual bits and pieces of domain knowledge (properties) and a large number of knowledge sources and services that provide mappings between sets of properties, the objective of the component set identification problem is to select a minimum cost combination of knowledge sources that can provide a joint mapping from a given set of initially available properties (initial knowledge) to a set of initially unknown properties (target knowledge). We provide a general framework for heuristics and consider construction heuristics that are followed by local improvement heuristics. Computational results are reported on randomly generated problem instances.