| EPSRC Reference: |
EP/H000666/1 |
| Title: |
Submodular optimization, lattice theory and maximum constraint satisfaction problems |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Engineering and Computing Sciences |
| Organisation: |
Durham, University of |
| Scheme: |
Standard Research |
| Starts: |
01 July 2010 |
Ends: |
31 March 2014 |
Value (£): |
297,257
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Sub- and supermodular functions are special functions defined on the powerset of a set. Such functions are a key concept in combinatorial optimization, and they have numerous applications elsewhere. The problem, SFM, of minimizing a given submodular function is one of the most important tractable optimization problems. Our first goal is to investigate algorithmic aspects of the SFM generalized to arbitrary finite lattices rather than just families of subsets (thus representing order different from that of inclusion). In our setting, the classical SFM would correspond to the simplest non-trivial case of the two-element lattice. We intend to find a new wide natural class of tractable optimization problems.Recently, a strong connection was discovered between the properties of sub- and supermodularity on lattices and tractability of the so-called maximum constraint satisfaction problems (Max CSP), which are very actively studied problems in computer science and artificial intelligence. In a Max CSP, one is given a collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to find an assignment of values from a fixed domain to the variables with a maximum number (or total weight) of satisfied constraints. We intend to investigate the full extent of this connection. We will also consider an extension of the Max CSP framework to valued, or soft, constraints that deal with desirability rather than just feasibility, and hence define a more general optimization problem. Thus, our second goal is to understand the reasons for tractability within a wide class of (generally hard) combinatorial optimization problems.
|
|
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: |
|