Dalmau V, Krokhin A, Manokaran R. Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs
We have relevant datasets, repositories, frameworks and tools of relevance for research and technology transfer initiatives related to knowledge extraction. This section provides an overview on a selection of them and links to download or contact details.
The MdM Strategic Research Program has its own community in Zenodo for material available in this repository
as well as at the UPF e-repository 
. Below a non-exhaustive list of datasets representative of the research in the Department.
As part of the promotion of the availability of resources, the creation of specific communities in Zenodo has also been promoted, at level of research communities (for instance, MIR and Educational Data Analytics) or MSc programs (for instance, the Master in Sound and Music Computing)
Dalmau V, Krokhin A, Manokaran R. Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs
Dalmau V, Krokhin A, Manokaran R. Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs
In this paper we study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language consisting of finitary functions on a fixed finite domain. An instance of VCSP is given by a finite set of variables and a sum of functions belonging to and depending on a subset of the variables. Each function takes values in [0, 1] specifying costs of assignments of labels to its variables, and the goal is to find an assignment of labels to the variables that minimizes the sum. A recent result of Ene et al. says that, under the mild technical condition that contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for VCSP unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP. We also show how these algebraic conditions can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation.
arXiv e-print: https://arxiv.org/abs/1610.01019