| 总结: | <p>Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.</p> <p>In Boolean surjective VCSPs variables take on labels from $D=\{0,1\}$ and an optimal assignment is required to use both labels from $D$. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for $\{0,\infty\}$-valued constraint languages (corresponding to CSPs) obtained by Creignou and H\&apos;ebrard, and the dichotomy for $\{0,1\}$-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.</p>
|
|---|