Minimization of locally defined submodular functions by optimal soft arc consistency
type: Item
instance of: scholarly article
title: Minimization of locally defined submodular functions by optimal soft arc consistency
zbMATH Open document ID: 1180.90262
author: M. C. Cooper
published in: Constraints
publication date: 2009-05-29T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5559828
zbMATH Keywords: discrete optimization
zbMATH Keywords: valued constraint satisfaction problem
zbMATH Keywords: soft constraints
zbMATH Keywords: majority operation
zbMATH Keywords: linear programming
MaRDI profile type: Publication
full work available at URL: s10601-007-9037-5
OpenAlex ID: W2005103485
cites work: Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
cites work: Pseudo-Boolean optimization
cites work: Combinatorial problems raised from 2-semilattices
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Principles and Practice of Constraint Programming – CP 2004
cites work: Q5715675
cites work: Supermodular functions and the complexity of MAX CSP
cites work: The complexity of soft constraint satisfaction
cites work: An Algebraic Characterisation of Complexity for Valued Constraint
cites work: Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
cites work: Reduction operations in fuzzy or valued constraint satisfaction
cites work: High-order consistency in valued constraint satisfaction
cites work: Arc consistency for soft constraints
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Minimum cuts, modular functions, and matroid polyhedra
cites work: On submodular function minimization
cites work: Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Submodular functions and optimization.
cites work: Realization of set functions as cut functions of graphs and hypergraphs
cites work: A new approach to the maximum-flow problem
cites work: Corrigendum to our paper ''The ellipsoid method and its consequences in combinatorial optimization''
cites work: A fully combinatorial algorithm for submodular function minimization.
cites work: A Faster Scaling Algorithm for Minimizing Submodular Functions
cites work: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
cites work: On the algebraic structure of combinatorial problems
cites work: Constraints, consistency and closure
cites work: Closure properties of constraints
cites work: Tractable constraints on ordered domains
cites work: The Approximability of Three-valued MAX CSP
cites work: The partial constraint satisfaction problem: Facets and lifting theorems
cites work: Solving weighted CSP by maintaining arc consistency
cites work: Generalized Arc Consistency for Positive Table Constraints
cites work: Q5292089
cites work: Submodular functions and electrical networks
cites work: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
cites work: Q4152462
cites work: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
cites work: Finding the nearest point in A polytope
DOI: 10.1007/S10601-007-9037-5
description: scientific article; zbMATH DE number 5559828