Generalized tangent cone and an optimization problem in a normed space

Most abstract multiplier rules in the literature are based on the tangential approximation at a point to some set in a Banach space. The present paper is concerned with the study of a generalized tangent cone, which is a tangential approximation to that set at a common point of two sets. The new notion of tangent cone generalizes previous concepts of tangent cones. This generalized tangent cone is used to characterize the optimality conditions for a simultaneous maximization and minimization problem. The paper is of theoretical character; practical applications are not found so far.     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.     

A cone programming approach to the bilinear matrix inequality problem and its geometry

We discuss an approach for solving the Bilinear Matrix Inequality (BMI) based on its connections with certain problems defined over matrix cones. These problems are, among others, the cone generalization of the linear programming (LP) and the linear complementarity problem (LCP) (referred to as the Cone-LP and the Cone-LCP, respectively). Specifically, we show that solving a given BMI is equivalent to examining the solution set of a suitably constructed Cone-LP or Cone-LCP. This approach facilitates our understanding of the geometry of the BMI and opens up new avenues for the development of the computational procedures for its solution. Research supported in part by the National Science Foundation under Grant CCR-9222734.     

On a clique covering problem of orlin

Let T_2n be the complement of a perfect matching in the complete graph on 2n vertices, and cc(T_2n) be the minimum number of complete subgraphs necessary to cover all the edges of T_2n Orlin posed the problem of determining the asymptotic behaviour of cc(T_2n). We show that $\text{cc}\text{(T}{}_{\mathrm{2n}}\text{)=}\text{min}\text{{k:n?(}\text{k?1}\text{?}\text{k}\text{2}\text{?}\text{)}}$ for all n>1, (which implies that lim_n→∞cc(T_2n)/log₂n=1). This is done by applying a Sperner-type theorem on set families due to Bollobás and Schönheim.     

On the structure of small strength‐2 covering arrays

A covering array $\text{CA}\left(N;t,k,v\right)$ of strength $t$ is an $N\times k$ array of symbols from an alphabet of size $v$ such that in every $N\times t$ subarray, every $t$‐tuple occurs in at least one row. A covering array is optimal if it has the smallest possible $N$ for given $t$, $k$, and $v$, and uniform if every symbol occurs $?N∕v?$ or $?N∕v?$ times in every column. Before this paper, the only known optimal covering arrays for $t=2$ were orthogonal arrays, covering arrays with $v=2$ constructed from Sperner's Theorem and the Erd?s‐Ko‐Rado Theorem, and 11 other parameter sets with $v>2$ and $N>v^2$. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength‐2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength‐2 covering array with $v>2$ and $N>v^2$ is now known for 21 parameter sets. Our constructive results continue to support the conjecture.     

On a problem about covering lines by squares

LetS be the square [0,n]² of side lengthn and letS = {S ₁, ...,S _t} be a set of unit squares lying insideS, whose sides are parallel to those ofS.S is called a line cover, if every line intersectingS also intersects someS _i S. Let(n) denote the minimum cardinality of a line cover, and let(n) be defined in the same way, except that we restrict our attention to lines which are parallel to either one of the axes or one of the diagonals ofS. It has been conjectured by Fejes Tóth that(n)=2n+O(1) and by Bárány and Füredi that(n)=3/2n+O(1). We will prove that, instead,(n)=4/3n+O(1) and, as to Fejes Tóth's conjecture, we will exhibit a noninteger solution to a related LP-relaxation, which has size equal to 3/2n+O(1).     

On the independent queens covering problem

The minimum number of queens which can be placed on ann × n chessboard so that all other squares are dominated by at least one queen but no queen covers another, is shown to be less than 0.705n + 2.305.     

On programming when the positive cone has an empty interior

In this note, we present a condition which is equivalent to the existence of the Lagrange multiplier for the general convex programming problem. This condition enables one to study a hypothesis distinct from the one of nonempty interior of the positive cone of the space of restrictions that is commonly used. Simple examples of this condition are given. We also explore the relationship of this condition with the subdifferentiability of the primal functional.     

On polyhedral extension of some LP theorems

McLinden (Mathematical Programming 24 (1982) 162–176) has extended theorems of Tucker (1956) and Williams (1970) on the complementarity behaviour of feasible and optimal solutions to a pair of canonical linear programs to proper convex polyhedral functions. He achieved this by heavily using the well-developed machinery of convex analysis. In this note, we prove most of his results mainly using linear programming theory.     

Cones with a mapping cone symmetry in the finite-dimensional case

In the finite-dimensional case, we present a new approach to the theory of cones with a mapping cone symmetry, first introduced by Størmer. Our method is based on a definition of an inner product in the space of linear maps between two algebras of operators and the fact that the Jamio?kowski-Choi isomorphism is an isometry. We consider a slightly modified class of cones, although not substantially different from the original mapping cones by Størmer. Using the new approach, several known results are proved faster and often in more generality than before. For example, the dual of a mapping cone turns out to be a mapping cone as well, without any additional assumptions. The main result of the paper is a characterization of cones with a mapping cone symmetry, saying that a given map is an element of such cone if and only if the composition of the map with the conjugate of an arbitrary element in the dual cone is completely positive. A similar result was known in the case where the map goes from an algebra of operators into itself and the cone is a symmetric mapping cone. Our result is proved without the additional assumptions of symmetry and equality between the domain and the target space. We show how it gives a number of older results as a corollary, including an exemplary application.     

An overview of graph covering and partitioning

While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.     

On the principal eigenvalue of a Robin problem with a large parameter

We study the asymptotic behaviour of the principal eigenvalue of a Robin (or generalised Neumann) problem with a large parameter in the boundary condition for the Laplacian in a piecewise smooth domain. We show that the leading asymptotic term depends only on the singularities of the boundary of the domain, and give either explicit expressions or two‐sided estimates for this term in a variety of situations. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On a covering problem related to the centered Hardy-Littlewood maximal inequality

We find the exact value of the best possible constant associated with a covering problem on the real line.     

Cone dominance and efficiency in DEA

This paper incorporates cones on virtual multipliers of inputs and outputs into DEA analysis. Cone DEA models are developed to generalize the dual of the BCC models as well as congestion models. Input-output data and/or numbers of DMUs for BCC models are inadequate to capture many aspects where judgments, expert opinions, and other external information should be taken into analysis. Cone DEA models, on the other hand, offer improved definitions of efficiency over general cone and polyhedral cone structures. The relationships between cone models and BCC models as well as those between cone models and congestion models are discussed in the development. Two numerical examples are provided to illustrate our findings.