Abstract

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints (MAX CSP) or, alternatively, to minimize the number of unsatisfied constraints (MIN CSP). This problem is usually parameterized by the set, Gamma, of relations allowed in the constraints, usually called constraint language. It turns out that MAX CSP/MIN CSP is computationally hard for most constraint languages, which motivates the study of approximation algorithms. In this talk we will focus on the approximation of MIN CSPs. We shall start addressing the following question: which constraint languages give rise to a MIN CSPs that is constant-factor approximable? We shall also study some other weaker approximation notions such polynomial loss and robust approximation.

Note

This talk is organized by the Algorithms and Complexity Group at the Institute of Computer Graphics and Algorithms and the Vienna Center for Logic and Algorithms (VCLA).

Speakers

• Victor Dalmau, TIC department, Universitat Pompeu Fabra, Spain

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.

Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!