AN ALGEBRAIC THEORY OF COMPLEXITY FOR DISCRETE OPTIMIZATION

作者：Cohen David A^*; Cooper Martin C; Creed Paidi; Jeavons Peter G; Zivny Stanislav

来源：SIAM Journal on Computing, 2013, 42(5): 1915-1939.

DOI：10.1137/130906398

• Galois connection
• constraint optimization
• discrete optimization
• valued constraint satisfaction problems
• weighted clones
• weighted polymorphisms

Discrete optimization problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimized can be expressed as a sum of functions of a restricted form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a finite-domain discrete optimization problem is determined by certain algebraic properties of the objective function, which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterized. These results provide a new approach to studying the complexity of discrete optimization. We use this approach to identify certain maximal tractable subproblems of the general problem and hence derive a complete classification of complexity for the Boolean case.

• 出版日期2013