图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem

We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.     

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

A Meta-heuristic with Orthogonal Experiment for the Set Covering Problem

This paper reports an evolutionary meta-heuristic incorporating fuzzy evaluation for some large-scale set covering problems originating from the public transport industry. First, five factors characterized by fuzzy membership functions are aggregated to evaluate the structure and generally the goodness of a column. This evaluation function is incorporated into a refined greedy algorithm to make column selection in the process of constructing a solution. Secondly, a self-evolving algorithm is designed to guide the constructing heuristic to build an initial solution and then improve it. In each generation an unfit portion of the working solution is removed. Broken solutions are repaired by the constructing heuristic until stopping conditions are reached. Orthogonal experimental design is used to set the system parameters efficiently, by making a small number of trials. Computational results are presented and compared with a mathematical programming method and a GA-based heuristic.     

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems

We prove that the existence of a polynomial time-approximation algorithm (where < 1 is a fixed constant)for a class of independent set problems, leads to a polynomial timeapproximation algorithm with approximation ratio strictly smallerthan 2 for vertex covering, while the non-existence of such analgorithm induces a lower bound on the ratio of every polynomialtime approximation algorithm for vertex covering. We also prove asimilar result for a (maximization) convex programming problemincluding quadratic programming as subproblem.     

Approximation algorithms for the test cover problem

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics. Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Partially supported by a Merck Computational Biology and Chemistry Program Graduate Fellowship from the Merck Company Foundation.Also Iceland Genomics CorporationPartially supported by subcontract No. 16082-RFP-00-2C in the area of ``Combinatorial Optimization in Biology (XAXE),' Los Alamos National Laboratories, and NSF grant CCR-0105548.Mathematics Subject Classification: 90B27     

一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

Genetic Algorithm for the Jump Number Scheduling Problem

This paper introduces genetic algorithms for the jump number scheduling problem. Given a set of tasks subject to precedence constraints, the problem is to construct a schedule to minimize the number of jumps. We show that genetic algorithms outperform the previously known Knuth and Szwarcfiter's exhaustive search algorithm when applied to some classes of orders in which no polynomial time algorithms exist in solving the jump number problem. Values for various parameters of genetic jump number algorithms are tested and results are discussed.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.     

基于背包模型的人员优化配置问题

运用背包模型解决油库人员在各岗位的优化配置问题,并运用贪婪算法进行求解.考虑到各人员的总工作时间的均衡性,运用反向排序的方法对原有的贪婪算法进行改进.最后,通过举例对两种算法进行评价.     

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。     

总延误问题顺时安排法的性能比

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加．工排列，使相应的总延误达到最小，这就是总延误问题．该问题在近年已被证明是NP困难的．由Wilkermn和Irwin（1971），林勋（1983）等所研究的顺时安排法能得到相邻交换意义下的局部解．在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比．     

Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem

Whereas CP methods are strong with respect to the detection of local infeasibilities, OR approaches have powerful optimization abilities that ground on tight global bounds on the objective. An integration of propagation ideas from CP and Lagrangian relaxation techniques from OR combines the merits of both approaches. We introduce a general way of how linear optimization constraints can strengthen their propagation abilities via Lagrangian relaxation. The method is evaluated on a set of benchmark problems stemming from a multimedia application. The experiments show the superiority of the combined method compared with a pure OR approach and an algorithm based on two independent optimization constraints.     

Cost Based Filtering for the Constrained Knapsack Problem

We present cost based filtering methods for Knapsack Problems (KPs). Cost based filtering aims at fixing variables with respect to the objective function. It is an important technique when solving complex problems such as Quadratic Knapsack Problems, or KPs with additional constraints (Constrained Knapsack Problems (CKPs)). They evolve, e.g., when Constraint Based Column Generation is applied to appropriate optimization problems. We develop new reduction algorithms for KP. They are used as propagation routines for the CKP with (nlogn) preprocessing time and (n) time per call. This sums up to an amortized time (n) for (logn) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

Generalized cover facet inequalities for the generalized assignment problem

The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.