An Algebraic Theory of Complexity for Discrete Optimisation

Abstract

Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function, which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach to studying the complexity of discrete optimisation. We use this approach to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification of complexity for the Boolean case.

26 pages, full version of three conference papers: CP'06, MFCS'11, and CP'11

References in corpus (5)

• The Power of Linear Programming for Valued CSPs
• The complexity of conservative valued CSPs
• The Expressive Power of Binary Submodular Functions
• Hybrid tractability of soft constraint problems
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation

Cited by in corpus (18)

• The Power of Linear Programming for Valued CSPs
• The power of linear programming for general-valued CSPs
• The complexity of finite-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• A finer reduction of constraint problems to digraphs
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Necessary conditions for tractability of valued CSPs
• The limits of SDP relaxations for general-valued CSPs
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• The complexity of Boolean surjective general-valued CSPs
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
• Constraint Satisfaction Problems over Finite Structures
• Binarisation for Valued Constraint Satisfaction Problems
• On a general framework for network representability in discrete optimization
• On Planar Valued CSPs
• Quantaloidal Approach to Constraint Satisfaction
• An Application of Farkas' Lemma to Finite-Valued Constraint Satisfaction Problems over Infinite Domains