Complexity of Optimization: Valued CSPs on Infinite Domains

Constraint satisfaction problems naturally appear in everyday life. Typical examples are scheduling problems such as finding a suitable time slot for a meeting. Very often not all constraints can be satisfied, for example, not all invited participants can attend the meeting due to incompatible schedules. This naturally motivates an optimization task - we assign costs to different conditions on the meeting and we try to minimize the sum of the costs of the conditions not satisfied. For instance, if an unavoidable condition is that the meeting has to take place on a working day between 8 and 16, then we think of the cost of this constraint (or rather its non-satisfaction) as infinite. On the other hand, we might allow some people not to be present at the meeting, each absence contributing a cost of 1; then minimizing the costs of the constraints of these people participating means minimizing the number of absences. Such satisfiability problems and their optimization variant can be modeled through the powerful mathematical framework of valued constraint satisfaction problems, where one tries to assign elements from a fixed domain (for example, time slots in a working week) to the variables while minimizing the cost of this assignment. In recent years, the computational complexity of constraint satisfaction problems and their variants has been extensively studied. This research led to a development of algebraic conditions which elegantly describe the border between the problems that can be solved efficiently and those that are computationally hard. The algebraic approach paved the way to a full complexity classification for valued constraint satisfaction problems on finite domains. However, many concrete problems, for instance scheduling or clustering problems, cannot be modeled over a finite domain. This motivates the focus of this project on valued constraint satisfaction problems on infinite domains. Such problems have been studied only scarcely and a suitable algebraic framework still needs to be developed. We restrict to a subclass of problems which, in spite of the variables taking values in an infinite domain, are in some sense similar to the case of a finite domain, and therefore likely to admit adaptation of the algebraic methods that were fruitful for finite domains. We expect this project to broaden the horizons in the research on constraint satisfaction problems and significantly improve the understanding of the mathematical structure of valued constraints.