Loading…
An Algebraic Theory of Complexity for Discrete Optimization
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...
Saved in:
Published in: | SIAM journal on computing 2013-01, Vol.42 (5), p.1915-1939 |
---|---|
Main Authors: | , , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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. [PUBLICATION ABSTRACT] |
---|---|
ISSN: | 0097-5397 1095-7111 |
DOI: | 10.1137/130906398 |