OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

An Algebraic Theory of Complexity for Discrete Optimization

Cohen, David A. and Cooper, Martin C. and Creed, Paidi and Jeavons, Peter G. and Zivny, Stanislav An Algebraic Theory of Complexity for Discrete Optimization. (2013) SIAM Journal on Computing, 42 (5). 1915-1939. ISSN 0097-5397

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1137/130906398


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.

Item Type:Article
Additional Information:Thanks to SIAM editor. The definitive version is available at http://epubs.siam.org/doi/abs/10.1137/130906398
HAL Id:hal-01122748
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of London (UNITED KINGDOM)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:04 Mar 2015 14:16

Repository Staff Only: item control page