Introduction to the Maximum Solution Problem

DOI10.1007/978-3-540-92800-3_10zbMath1171.68499OpenAlexW1496829128MaRDI QIDQ5504706

Peter Jonsson, Gustav Nordh

Publication date: 22 January 2009

Published in: Complexity of Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

The Complexity of General-Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ PTAS for Sparse General-valued CSPs ⋮ The Complexity of Valued CSPs ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• An efficient algorithm for a class of constraint satisfaction problems
• A new tractable class of constraint satisfaction problems
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• On weighted vs unweighted versions of combinatorial optimization problems
• List homomorphisms and circular arc graphs
• A dichotomy for minimum cost graph homomorphisms
• The complexity of soft constraint satisfaction
• Complexity of clausal constraints over chains
• Level of repair analysis and minimum cost homomorphisms of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Constraint Satisfaction with Countable Homogeneous Templates
• An Algebraic Characterisation of Complexity for Valued Constraint
• The Maximum Solution Problem on Graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• MAX ONES Generalized to Larger Domains
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On Finding Critical Independent and Vertex Sets
• Approximation algorithms for NP-complete problems on planar graphs
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Closure properties of constraints
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• The complexity of maximal constraint languages
• Automated Reasoning
• Classifying the Complexity of Constraints Using Finite Algebras
• Some optimal inapproximability results
• The Approximability of Three-valued MAX CSP
• Mathematical Foundations of Computer Science 2005
• Generalised Integer Programming Based on Logically Defined Relations
• Tractable constraints on ordered domains

This page was built for publication: Introduction to the Maximum Solution Problem