| Autor: |
Vladimir Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin |
| Jazyk: |
angličtina |
| Rok vydání: |
2005 |
| Předmět: |
|
| Zdroj: |
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AE,..., Iss Proceedings (2005) |
| Druh dokumentu: |
article |
| ISSN: |
1365-8050 |
| DOI: |
10.46298/dmtcs.3420 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
