Details of Grant 

EPSRC Reference:	EP/F01161X/1
Title:	The complexity of valued constraints
Principal Investigator:	Jeavons, Professor PG
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Oxford
Scheme:	Standard Research
Starts:	01 October 2007	Ends:	30 September 2010	Value (£):	125,485
EPSRC Research Topic Classifications:	Algebra & Geometry Complexity Science Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:	EP/F011776/1
Panel History:	Panel Date Panel Name Outcome 19 Jul 2007 ICT Prioritisation Panel (Technology) Announced
Summary on Grant Application Form
This proposal is a collaborative application involving Professor Peter Jeavons at the University of Oxford, Professor David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France.We are seeking funding to extend and develop a novel algebraic theory of complexity for valued constraint satisfaction problems.Constraint satisfaction problems arise in many practical problems, such as scheduling and circuit layout, so this family of problems has been widely studied in computer science. All known algorithms for the most general form of the problem require exponential time, and are therefore impractical for large cases. However, several restrictions have been identified which are sufficient to make the restricted form of the problem efficiently solvable. In fact, a careful mathematical analysis of the problem has shown that the computational difficulty of any particular constraint satisfaction problem is closely related to certain algebraic properties of the constraints. In this research project we are seeking to develop a new algebraic approach to an even wider class of problems which involve both constraint satisfaction and optimisation. Such problems are called valued constraint problems. We hope to show that by using general algebraic methods we can identify all types of valued constraints which can be efficiently optimised. We also plan to implement the techniques we develop in new software tools which can be use to analyse any given example of a valued constraint problem, and solve it using special-purpose efficient methods when these are applicable.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic 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.ox.ac.uk