Geodesic
Supermodularity on chains and complexity of maximum constraint satisfaction
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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) of satisfied constraints. This problem is $\mathrm{NP}$-hard in general so it is natural to study how restricting the allowed types of constraints affects the complexity of the problem. In this paper, we show that any $\mathrm{Max \; CSP}$ problem with a finite set of allowed constraint types, which includes all constants (i.e. constraints of the form $x=a$), is either solvable in polynomial time or is $\mathrm{NP}$-complete. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known combinatorial property of supermodularity. 
@article{DMTCS_2005_special_250_a29,
     author = {Deineko, Vladimir and Jonsson, Peter and Klasson, Mikael and Krokhin, Andrei},
     title = {Supermodularity on chains and complexity of maximum constraint satisfaction},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3420},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3420/}
}
TY  - JOUR
AU  - Deineko, Vladimir
AU  - Jonsson, Peter
AU  - Klasson, Mikael
AU  - Krokhin, Andrei
TI  - Supermodularity on chains and complexity of maximum constraint satisfaction
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3420/
DO  - 10.46298/dmtcs.3420
LA  - en
ID  - DMTCS_2005_special_250_a29
ER  - 
%0 Journal Article
%A Deineko, Vladimir
%A Jonsson, Peter
%A Klasson, Mikael
%A Krokhin, Andrei
%T Supermodularity on chains and complexity of maximum constraint satisfaction
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3420/
%R 10.46298/dmtcs.3420
%G en
%F DMTCS_2005_special_250_a29
Deineko, Vladimir; Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei. Supermodularity on chains and complexity of maximum constraint satisfaction. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3420. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3420/

Cité par Sources :