An algebraic theory of complexity for discrete optimization.

DOI10.1137/130906398MaRDI QIDQ5396951zbMATH OpenOpenAlexFDO

Authors M. C. Cooper, Páidí Creed, S. Zivny, David A. Cohen, P. Jeavons

Publication date 4 February 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.6692, http://oatao.univ-toulouse.fr/12741/1/Cohen_12741.pdf

zbMATH Keywords

complexity of valued constraint languagesconstraint optimizationdiscrete optimizationGalois connectionsvalued constraint satisfaction problemweighted clonesweighted polymorphisms

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

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.

Recommendations

• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• An Algebraic Characterisation of Complexity for Valued Constraint
• Algebraic properties of valued constraint satisfaction problem
• An Algebraic Approach to Valued Constraint Satisfaction
• The complexity of conservative valued CSPs

Cited in

(37)

• On a general framework for network representability in discrete optimization
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Research on the efficient computation mechanism -- in the case of N-vehicle exploration problem
• On planar valued CSPs
• The complexity of soft constraint satisfaction
• An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains
• Tractability in constraint satisfaction problems: a survey
• The constraint satisfaction problem and universal algebra
• On a general framework for network representability in discrete optimization (extended abstract)
• Minimax problems of discrete optimization invariant under majority operators
• Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
• An algebraic theory of complexity for valued constraints: establishing a Galois connection
• A Galois connection for valued constraint languages of infinite size
• Algebraic properties of valued constraint satisfaction problem
• Necessary conditions for tractability of valued CSPs
• An Algebraic Characterisation of Complexity for Valued Constraint
• scientific article; zbMATH DE number 4020848 (Why is no real title available?)
• A Galois connection for weighted (relational) clones of infinite size
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Hybrid tractable classes of constraint problems
• The complexity of valued CSPs
• The lattice and semigroup structure of multipermutations
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• Soft constraints: complexity and multimorphisms
• Principles and Practice of Constraint Programming – CP 2004
• Quantaloidal approach to constraint satisfaction
• mathlib4 Module Mathlib/Combinatorics/Optimization/ValuedCSP
• The complexity of resilience problems via valued constraint satisfaction problems
• Algebraic approach to approximation
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Temporal valued constraint satisfaction problems
• The complexity of resilience problems via valued constraint satisfaction

This page was built for publication: An algebraic theory of complexity for discrete optimization.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5396951)