Sparsification of binary CSPs
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 introduction by Bencz´ur and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applica...
Main Authors: | , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Society for Industrial and Applied Mathematics
2020
|