Supermodularity on chains and complexity of maximum constraint satisfaction

Supermodularity on chains and complexity of maximum constraint satisfaction

In the maximum constraint satisfaction problem ($\mathrm{Max \; CSP}$), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximise the number (or the total weight...

Full description

Bibliographic Details
Main Authors: Vladimir Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2005-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
maximum constraint satisfaction
complexity
supermodularity
monge properties
digraph $h$-colouring
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
Online Access:https://dmtcs.episciences.org/3420/pdf

Internet

https://dmtcs.episciences.org/3420/pdf

Similar Items