An Algebraic Theory of Complexity for Discrete Optimization
| Autor: | Peter Jeavons, David Cohen, Páidí Creed, Stanislav Zivny, Martin C. Cooper |
|---|---|
| Přispěvatelé: | Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), University of London (UNITED KINGDOM), University of Oxford (UNITED KINGDOM), Department of Computer Science, University College of London [London] (UCL), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), School of Mathematical Sciences [London], Queen Mary University of London (QMUL), Department of Computer Science [Oxford], University of Oxford [Oxford], Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE) |
| Rok vydání: | 2013 |
| Předmět: |
FOS: Computer and information sciences
Algebraic properties Discrete Mathematics (cs.DM) General Computer Science Closed set General Mathematics General problem 0102 computer and information sciences Weighted Polymorphisms Computational Complexity (cs.CC) Galois connection 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] Discrete Optimization Weighted Clones 0101 mathematics Mathematics Logique en informatique 010102 general mathematics [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Informatique et langage Intelligence artificielle Galois Connection Apprentissage Algebra Computer Science - Computational Complexity 010201 computation theory & mathematics Algebraic theory Constraint Optimization Valued Constraint Satisfaction Problems F.2.0 Computer Science - Discrete Mathematics |
| Zdroj: | SIAM Journal on Computing SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, vol. 42 (n° 5), pp. 1915-1939. ⟨10.1137/130906398⟩ |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/130906398 |
| Popis: | Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised 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 optimisation 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 characterised. These results provide a new approach to studying the complexity of discrete optimisation. 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. 26 pages, full version of three conference papers: CP'06, MFCS'11, and CP'11 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|