Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/H000666/1 - Submodular optimization, lattice theory and maximum constraint satisfaction problems

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPH0006661.png

Professor A Krokhin EP/H000666/1 - Submodular optimization, lattice theory and maximum constraint satisfaction problems

Principal Investigator - Engineering and Computing Sciences, Durham University

Scheme

Standard Research

Research Areas

Maths of Computing Maths of Computing

Start Date

07/2010

End Date

12/2013

Value

£297,257

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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.

Structured Data / Microdata


Grant Event Details:
Name: Submodular optimization, lattice theory and maximum constraint satisfaction problems - EP/H000666/1
Start Date: 2010-07-01T00:00:00+00:00
End Date: 2013-12-31T00:00:00+00:00

Organization: Durham University

Description: 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 functi ...