×

An algebraic theory of complexity for discrete optimization. (English) Zbl 1305.08007

The aim of this paper is to present a unifying theory of complexity for problems of discrete optimization. It is a generalization of an algebraic theory developed over the past years. An instance of a problem of discrete optimization is specified by a set of variables, a set of possible values of these variables and a set of constraints. Each combination of values has an associated cost and the aim is to find an assignment with the minimal cost. Each type of constraint is described by rational valued functions and a set of these functions characterizing a given problem is a valued constraint language.
It is shown that the complexity of any valued constraint language over a finite domain with rational-valued costs is determined by certain algebraic properties which are called weighted polymorphisms. It is proved that the weighted polymorphisms of a valued constraint language are sufficient to determine the complexity of this language. Further a Galois connection between valued constraint languages and sets of weighted polymorphisms is stated. The closed sets on both sides of this Galois connection are characterized. The Galois connection is used in the search of tractable weighted constraint languages. Every tractable valued constraint language is characterized by an associated weighted clone (that is a generalization of the notion ‘clone of algebras’ or ‘clone of topological space’). Finally these results are used for a complete characterization of discrete optimization problem over Boolean domain. Several open problems are given at the end of this paper.

MSC:

08A70 Applications of universal algebra in computer science
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68W40 Analysis of algorithms
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv Link