Sparsification of binary CSPs
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Butti, Silvia
- dc.contributor.author Stanislav Zivný
- dc.date.accessioned 2020-03-26T13:04:01Z
- dc.date.available 2020-03-26T13:04:01Z
- dc.date.issued 2020
- dc.description.abstract A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their intro- duction by Bencz´ur and Karger [STOC’96], cut sparsifiers have proved extremely influen- tial and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA’17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains.en
- dc.description.sponsorship Stanislav ˇZivn´y was supported by a Royal Society University Research Fellowship. Work mostly done while Silvia Butti was at the University of Oxford. The project that gave rise to these results received the support of a fellowship from “a Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Unions Horizon 2020 research and innovation programme grant agreement No 714530 and under the Marie Sk lodowska-Curie grant agreement No 713673.
- dc.format.mimetype application/pdf
- dc.identifier.citation Butti S, Zivný S. Sparsification of binary CSPs. SIAM J Discret Math. 2020 Mar 23;34(1):825–42. DOI: 10.1137/19M1242446
- dc.identifier.doi http://dx.doi.org/10.1137/19M1242446
- dc.identifier.issn 0895-4801
- dc.identifier.uri http://hdl.handle.net/10230/44049
- dc.language.iso eng
- dc.publisher SIAM (Society for Industrial and Applied Mathematics)
- dc.relation.ispartof SIAM journal on discrete mathematics. 2020 Mar 23;34(1):825–42.
- dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/714530
- dc.rights © Society for Industrial and Applied Mathematics
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Constraint satisfaction problemsen
- dc.subject.keyword Minimum cutsen
- dc.subject.keyword Sparsificationen
- dc.title Sparsification of binary CSPs
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion