An Algebraic Theory of Complexity for Discrete Optimization

DOI10.1137/130906398zbMath1305.08007arXiv1207.6692OpenAlexW2071152266MaRDI QIDQ5396951

Stanislav Živný, Páidí Creed, Martin C. Cooper, Peter G. Jeavons, David A. Cohen

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

zbMATH Keywords

discrete optimizationGalois connectionsconstraint optimizationvalued constraint satisfaction problemweighted clonesweighted polymorphismscomplexity of valued constraint languages

Mathematics Subject Classification ID

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

Related Items (22)

Tractability in constraint satisfaction problems: a survey ⋮ The Complexity of General-Valued CSPs ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ On a general framework for network representability in discrete optimization ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ The lattice and semigroup structure of multipermutations ⋮ On planar valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ The Power of Linear Programming for General-Valued CSPs

This page was built for publication: An Algebraic Theory of Complexity for Discrete Optimization