Thesis icon

Thesis

The complexity and expressive power of valued constraints

Abstract:

This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Research group:
Constraints
Oxford college:
Keble College
Role:
Author

Contributors

Division:
MPLS
Department:
Computer Science
Role:
Supervisor
More from this funder
Name:
Engineering and Physical Sciences Research Council
Funding agency for:
Zivny, S
Grant:
EP/F01161X/1
Publication date:
2009
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
Oxford University, UK
Language:
English
Keywords:
Subjects:
UUID:
uuid:63facf22-7c2b-4d4a-8b6f-f7c323759ca0
Local pid:
ora:3029
Deposit date:
2009-11-05

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP