Sparsification of binary CSPs
| 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 problems | en |
| dc.subject.keyword | Minimum cuts | en |
| dc.subject.keyword | Sparsification | en |
| dc.title | Sparsification of binary CSPs | |
| dc.type | info:eu-repo/semantics/article | |
| dc.type.version | info:eu-repo/semantics/acceptedVersion |
Fitxers
Paquet original
1 - 1 de 1
Carregant...
- Nom:
- butti_siam34_spar.pdf
- Mida:
- 256.54 KB
- Format:
- Adobe Portable Document Format