Approximation of MIN CSP
An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables.
- Starts at
TU Wien, Campus Favoritenstraße
Seminarraum FAV EG C Gödel
1040 Vienna, Favoritenstraße 9-11
Erdgeschoß, HBEG10, HBEG10
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.
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).
- Victor Dalmau, TIC department, Universitat Pompeu Fabra, Spain
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!