EPSRC Reference: 
EP/M009408/1 
Title: 
Randomized approaches to combinatorial packing and covering problems 
Principal Investigator: 
Kuehn, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
Standard Research 
Starts: 
01 March 2015 
Ends: 
28 February 2018 
Value (£): 
258,260

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
10 Sep 2014

EPSRC Mathematics Prioritisation Panel Sept 2014

Announced


Summary on Grant Application Form 
Many important questions can be formulated as covering and packing problems. This makes the study of such problems crucial both from an algorithmic and a more structural point of view. Recent ideas and methods from discrete probability theory have led to several breakthroughs in the area, with the potential to reshape the field.
Here in a packing problem the task is to organize as many elements of a given structure as possible into suitable disjoint substructures. In a covering problem the task is to cover all elements of a given structure by as few as possible suitable substructures (which are not necessarily disjoint). These problems can be viewed as "duals" of each other. In particular, their solutions sometimes coincide, in which case we obtain a decomposition of the given structure.
A classical example occurs in design theory: under suitable divisibility conditions a Steiner Triple System gives a decomposition of the edges of a complete graph into edgedisjoint triangles, i.e. the optimal solution of the triangle packing problem equals that of the triangle covering problem. Such problems have a long history going back to the 19th century and have many applications, e.g. to testing, statistical design and coding theory.
The project intends to approach longstanding questions concerning optimal packings in noncomplete host graphs. These have applications e.g. in communication networks. Another related strand is to study packings and coverings involving more complex structures such as spanning trees and resolvable designs. We intend to provide a powerful algorithmic tool for such questions which can be viewed as nearoptimal packing version of the famous Blowup Lemma. This would have numerous structural and algorithmic applications. Furthermore, the packing and covering viewpoint can be valuable in a much broader context. In particular, we propose to employ it to study the Boolean Satisfiability Problem kSAT. The kSAT problem is computationally intractable and of fundamental importance in theoretical computer science. Again, the probabilistic perspective has proved to be invaluable. By formulating the kSAT problem as a hypergraph covering problem, we will aim to solve key open problems regarding statistical properties of random kSAT formulas.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.bham.ac.uk 