Discrete Optimisation and Combinatorial Geometry

Discrete Optimization and Lattices

farey This topic of our interest is devoted to applications of the Minkowski geometry of numbers to a series of discrete optimisation problems. The current research activities are focused on the geometry and combinatorics of integer knapsacks, lattice bases, integral generating sets and Hilbert bases. For instance, we recently applied the results on distribution of integer sublattices to derive new upper bounds for asymptotic growth of the Frobenius number in average (Aliev and Henk 2008). This research theme brings together researchers from Cardiff University, Vienna University of Technology (Prof. Peter Gruber and his group), University of Magdeburg (Prof. Martin Henk and his group) and other institutions worldwide.

Integer Polynomial Programming

This research topic belongs to Nonlinear Integer Programming and devoted to the study of algorithms for optimizing over integer polynomial programs. Integer polynomial programs are an important generalization of linear integer programs, the constraints of a polynomial program are given by polynomial inequalities in several variables. The algorithms to be designed are based on generalizations of various results from the theory of linear integer programming. We are planning to use powerful tools from the computational algebraic geometry to explore representations of lattice points by means of rational functions. At the same time we will try to follow the basic algorithmic streamline in integer programming. We expect various theoretical results about the structure of the set of feasible solutions of an integer program. This research topic is developing in collaboration with University of Magdeburg (Prof. Martin Henk and his group).

Existence Theorems in Discrete Search

As an example, consider the following group testing problem. Let a set of n factors is given and assume that only some of them are significant. Let T be the (unknown) group of significant factors. It is required to determine T by testing as few as possible factor groups. Assume that the result of the test for the factor group X can be written in the form f(X,T) = min {K, N(X,T)}, where N(X,T) is the number of elements in the intersection of X and T and K is an integer. (In binary screening problems K=1, in the multiaccess channel problem K=2 and in additive screening K=n.) To prove existence of a deterministic design of length N separating all factor groups it is enough to prove that the probability of separation of these groups is positive for a random design. Using this general principle suggested in an early work of A.Renyi, we can derive upper bounds for the length of optimal nonsequential group testing designs in different cases when the information about the number of elements in T and X is available. A general way of derivation of asymptotic upper bounds, when n tends to infinity, is also available. The technique is applied to many discrete search problems including searching with lies.

Asymptotic Distributions in Diophantine Approximations

Another example deals with the accuracy of diophantine approximations expressed in probabilistic terms. Many diophantine approximation algorithms produce a sequence of sets F(n), indexed by n, of rational numbers p/q in [0,1]. Famous examples of F(n) are the Farey sequence, the collection of rationals p/q in [0,1] with q<=n, and the collection of all n-th continued fraction convergents. We consider several related accuracy characteristics of F(n) such as the average length of the uncertainty interval for a random x in [0,1], Renyi entropies of the partitions generated by the points in F(n), and the two-dimensional distribution of the distances between random x and both endpoints of the uncertainty interval. Properly normalized, these characteristics are expected to exhibit certain asymptotic behaviour when n tends to infinity. The corresponding results can typically be expressed in probabilistic language, in terms of weak convergence of sequences of probability measures if x is treated as a random point uniformly distributed on [0,1].

Studying the limiting probability distributions and the rate of convergence to them constitutes the main objective of the work in this direction.

Cardiff Investigators


Collaborators

Selected publications