On the complexity of sequentially lifting cover inequalities for the knapsack polytope

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs.However,it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover(Gu et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.     

A linear-time approximation algorithm for the weighted vertex cover problem

A linear time approximation algorithm for the weighted set-covering problem is presented. For the special case of the weighted vertex cover problem it produces a solution of weight which is at most twice the weight of an optimal solution.     

Covering a plane with ellipses

Abstract

This paper is devoted to the construction of regular min-density plane coverings with ellipses of one, two and three types. This problem is relevant, for example, to power-efficient surface sensing by autonomous above-grade sensors. A similar problem, for which discs are used to cover a planar region, has been well studied. On the one hand, the use of ellipses generalizes a mathematical problem; on the other hand, it is necessary to solve these types of problems in real applications of wireless sensor networks. This paper both extends some previous results and offers new regular covers that use a small number of ellipses to cover each regular polygon; these covers are characterized by having minimal known density in their classes and give the new upper bounds for densities in these classes as well.     

Injective and flat covers,envelopes and resolvents

Using the dual of a categorical definition of an injective envelope, injective covers can be defined. For a ringR, every leftR-module is shown to have an injective cover if and only ifR is left noetherian. Flat envelopes are defined and shown to exist for all modules over a regular local ring of dimension 2. Using injective covers, minimal injective resolvents can be defined.     

完备强对偶原子分配格上的不可约极小并分解及其应用

在完备强对偶原子分配格上引入了不可约极小并分解的概念,给出了元素存在不可约极小并分解的一些充要条件.证明了当元素恰有一个下邻时,该元索就足完全并既约元;有两个下邻时,元素的不可约极小并分解与不可约完全并既分解是等价的;下邻多于两个时,元素的不可约极小并分解不一定足不可约完全并既分解.最后证明了模糊关系方程有极小解的充要条件是方程左边有大于等于右手项的系数或右手项系数有不可约极小并分解.     

On the complexity of enumerating pseudo-intents

We investigate whether the pseudo-intents of a given formal context can efficiently be enumerated. We show that they cannot be enumerated in a specified lexicographic order with polynomial delay unless P=NP. Furthermore we show that if the restriction on the order of enumeration is removed, then the problem becomes at least as hard as enumerating minimal transversals of a given hypergraph. We introduce the notion of minimal pseudo-intents and show that recognizing minimal pseudo-intents is polynomial. Despite their less complicated nature, surprisingly it turns out that minimal pseudo-intents cannot be enumerated in output-polynomial time unless P=NP.     

Bimatroidal independence systems

An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F _M) andN=(X, F _N) such thatF=F _M∪ F_N. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.     

Linearly ordered covers,normality and paracompactness

It is shown that a regular space is collectionwise normal and countably paracompact if every open cover has an open, order cushioned refinement. A sufficient condition for paracompactness, in terms of certain order locally finite covers, is given, and is applied to the problem of the paracompactness of product spaces.     

On the computational complexity of a merge recognition problem

A problem arising from the work of C.A.R. Hoare on parallel programming is that of deciding whether a given string ? is a “merge” of two other given strings σ and τ. We describe a polynomial time algorithm for this problem. This algorithm can easily be extended to check, in polynomial time, whether ? is a merge of any fixed number of strings. The problem for an arbitrary number of strings is shown to be NP-complete and so is unlikely to have a polynomial time algorithm.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

Irredundant and Minimal Covers of Finite Groups

A cover of a finite noncyclic group G is a family ? of proper subgroups of G whose union equals G. A cover of G is called minimal if it has minimal size, and irredundant if it does not properly contain any other cover. We classify the finite noncyclic groups all of whose irredundant covers are minimal.     

Theoretical Complexity of Grid Cover Problems Used in Radar Applications

Modern radars are highly flexible systems, relying on digital antennas to dynamically control the radar beam shape and position through electronic circuits. Radar surveillance is performed by sequential emission of different radar beams. Optimization of radar surveillance requires finding a minimal subset of radar beams, which covers and ensures detection over the surveillance space, among a collection of available radar beams with different shapes and positions, thus minimizing the required scanning time. Optimal radar surveillance can be modelled by grid covering, a specific geometric case of set covering where the universe set is laid out on a grid, representing the radar surveillance space, which must be covered using available subsets, representing the radar beams detection areas. While the set cover problem is generally difficult to solve optimally, certain geometric cases can be optimized in polynomial time. This paper studies the theoretical complexity of grid cover problems used for modelling radar surveillance, proving that unidimensional grids can be covered by strongly polynomial algorithms based on dynamic programming, whereas optimal covering of bidimensional grids is generally non-deterministic polynomially hard.     

k-边覆盖对策及其核心

本文针对从图的k-边覆盖问题引出的合作对策模型，利用线性规划对偶理论得到了其核心非空的一个充分条件和构造核心分配的多项式时间算法，并将这一结果推广到了一般的k-集合覆盖对策模型中．     

Application of a location model to fire stations in Rotterdam

This report is an outgrowth of a research project carried out by the Operations Research Group of Twente University of Technology in cooperation with the Department Fire-Brigade Affairs (Home Office) and the Rotterdam Fire Department. The objectives of the project were to determine the minimal number of fire stations, their locations and the number of first attendance pumpers, so that each point in town can be reached within a prescribed attendance time with sufficient equipment.A road network approach was used for determining the set of possible location areas for fire stations followed by a set-covering approach for calculating the minimal number of stations. The hard points to tackle were the construction of robust networks, the determination of the possible location areas and the calculation of all the alternative locations of a minimal number of fire stations.A simulation was carried out to test whether the solutions given by the network approach were realistic.     

1-factor covers of regular graphs

We consider minimal 1-factor covers of regular multigraphs, focusing on those that are 1-factorizations. In particular, we classify cubic graphs such that every minimal 1-factor cover is also a 1-factorization, and also classify simple regular bipartite graphs with this property. For r>3, we show that there are finitely many simple r-regular graphs such that every minimal 1-factor cover is also a 1-factorization.     

Enumerating pseudo-triangulations in the plane

In this paper, we study the problem of whether a polyhedron can be obtained from a net by folding along the creases. We show that this problem can be solved in polynomial time if the dihedral angle at each crease is given, and it becomes NP-hard if these angles are unknown. We also study the case when the net has rigid faces that should not intersect during the folding process.     

Invariant measures for the horocycle flow on periodic hyperbolic surfaces

We classify the ergodic invariant Radon measures for the horocycle flow on geometrically infinite regular covers of compact hyperbolic surfaces. The method is to establish a bijection between these measures and the positive minimal eigenfunctions of the Laplacian of the surface. Two consequences arise: if the group of deck transformations G is of polynomial growth, then these measures are classified by the homomorphisms from G ₀ to ℝ where G ₀ ≤ G is a nilpotent subgroup of finite index; if the group is of exponential growth, then there may be more than one Radon measure which is invariant under the geodesic flow and the horocycle flow. We also treat regular covers of finite volume surfaces. The first author was supported by NSF grant 0500630. The second author was supported by NSF grant 0400687.     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Costing communication standards in information systems using a minimum cut approach

On a very abstract level, an information system consists of a set of system elements which communicate with each other. Communication is an unproductive operation, so the time needed to communicate data should be kept as short as possible and, to put it in monetary terms, the opportunity costs for communication should be kept small. Now, communicating data is more than just transmitting it; it consists in large parts of converting data structures that are used by one system element into data structures that are used by another system element. Such conversion can be avoided, if the system elements, use a common standard of data structures. Since establishing a standard at a system element incurs standardization costs, a decision-maker has to check, if the cost savings gained by standardized communication outweigh the costs for installing the standard. In a recent paper by Buxmann et al¹, it is claimed that this so-called standardization problem is an NP-hard optimization problem without giving a formal proof for it. We will demonstrate that this claim is not true, but in fact the standardization problem can be solved in polynomial time by solving a minimum cut problem.     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.