An Improvement of an Inequality Linking Packing and Covering Densities in 3-space

It is shown that if K is a compact convex set which is centrally symmetric and has a nonempty interior, then the density of the tightest lattice packing with copies of K in Euclidean 3-space divided by the density of the thinnest lattice covering of Euclidean 3-space with copies of K is greater than or equal to 1/3. This improves the previous bound in [5] of 1/4. It is possible this bound will be improved in the future, though not beyond approximately 1/2     

On the Universal Splitting Property

We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low₂. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.     

Logical analysis of numerical data

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others. The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083).     

Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

A location is sought within some convex region of the plane for the central site of some public service to a finite number of demand points. The parametric maxcovering problem consists in finding for eachR>0 the point from which the total weight of the demand points within distanceR is maximal. The parametric minimal quantile problem asks for each percentage α the point minimising the distance necessary for covering demand points of total weight at least α. We investigate the properties of these two closely related problems and derive polynomial algorithms to solve them both in case of either (possibly inflated) Euclidean or polyhedral distances. The research of the first author is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educación y Cultura, Spain.     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On minquantile and maxcovering optimisation

In this paper we introduce the parametric minquantile problem, a weighted generalisation ofkth maximum minimisation. It is shown that, under suitable quasiconvexity assumptions, its resolution can be reduced to solving a polynomial number of minmax problems.It is also shown how this simultaneously solves (parametric) maximal covering problems. It follows that bicriteria problems, where the aim is to both maximize the covering and minimize the cover-level, are reducible to a discrete problem, on which any multiple criteria method may be applied.Corresponding author.Visiting researcher at the Center for Industrial Location of the Vrije Universiteit Brussel during this research.     

Universal forcing notions and ideals

Our main result states that a finite iteration of Universal Meager forcing notions adds generic filters for many forcing notions determined by universality parameters. We also give some results concerning cardinal characteristics of the σ-ideals determined by those universality parameters. Both authors acknowledge support from the United States-Israel Binational Science Foundation (Grant no. 2002323). Also, we would like to thank the referee for valuable comments and suggestions concerning the exposition of the paper. This is publication 845 of the second author     

Exceptional Modules for Tubular Canonical Algebras

Let Λ be a tubular canonical algebra of quiver type over a field. We show that each exceptional Λ-module can be exhibited by matrices involving as coefficients 0, 1 and –1 if Λ is of type (3,3,3), (2,4,4) or (2,3,6) and by matrices involving as coefficients 0, 1, –1, λ, –λ and λ–1 if Λ is of type (2,2,2,2) and defined by a parameter λ. Presented by Claus M. Ringel.     

Azimuthal Shear in Compressible Finite Elasticity

In an earlier paper, the broadest classes of compressible isotropic strain energies that support irrotational universal deformations were identified and the problems of cylindrical and spherical inflation or compaction were solved in closed form for all of these strain energies. Similar closed form solutions of the problem of azimuthal shear are presented here.      

A few uncaught universal Hermitian forms

We will complete the list of universal binary Hermitian forms over imaginary quadratic fields by investigating three Hermitian forms missed by previous researchers.