Events

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.

Bio: Associate Professor at the Department of Information Technologies, Universitat Pompeu Fabra, Barcelona, Spain. He obtained a degree and a Ph.D on Computer Science at Universitat Politécnica de Catalunya, Spain. His main research is on Constraint satisfaction, which is the problem of deciding whether there exists an assignment of values to variables satisfying some given restrictions. The framework is general enough to express many common problems in areas such as logistics, computer vision, scheduling, and artificial intelligence, to name only a few. His work focuses on the theoretical aspects of the problem, involving techniques and concepts coming from areas as diverse as combinatorics, logic, database theory and universal algebra. He is also interested broadly in complexity theory, logic in computer science, and computational learning theory. He has published 23 journal papers and 29 conference (peer-reviewed) papers. He received the “Ramón y Cajal” Fellowship and the ICDT 2012 best paper award.

Date: Friday 27th April 2018, 10.00.-

Place: Auditorio San Agustín, Campus San Joaquín, Pontificia Universidad Católica, Santiago. Chile.