Additive sparsification of CSPs

Additive sparsification of CSPs

Show other versions (1)

Multiplicative cut sparsifiers, introduced by Bencz´ur and Karger [STOC’96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifiability of graphs with other 2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDM...

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Pelleg, E, Zivny, S
Format:	Journal article
Sprog:	English
Udgivet:	Association for Computing Machinery 2023

Lignende værker

Additive sparsification of CSPs
af: Pelleg, E, et al.
Udgivet: (2021)

Sparsification of binary CSPs
af: Butti, S, et al.
Udgivet: (2020)

Sparsification of Binary CSPs
af: Butti, S, et al.
Udgivet: (2019)

On planar valued CSPs
af: Fulla, P, et al.
Udgivet: (2016)

On planar valued CSPs
af: Fulla, P, et al.
Udgivet: (2017)

The complexity of finite-valued CSPs
af: Thapper, J, et al.
Udgivet: (2016)

The complexity of conservative valued CSPs
af: Kolmogorov, V, et al.
Udgivet: (2012)

The complexity of conservative valued CSPs
af: Kolmogorov, V, et al.
Udgivet: (2011)

The complexity of conservative valued CSPs
af: Kolmogorov, V, et al.
Udgivet: (2013)

The Complexity of Finite-Valued CSPs
af: Thapper, J, et al.
Udgivet: (2013)

The complexity of finite-valued CSPs
af: Thapper, J, et al.
Udgivet: (2013)

Pliability and approximating max-CSPs
af: Romero, M, et al.
Udgivet: (2023)

Point-width and Max-CSPs
af: Carbonnel, C, et al.
Udgivet: (2020)

Point-width and max-CSPs
af: Carbonnel, C, et al.
Udgivet: (2019)

The complexity of conservative finite-valued CSPs
af: Kolmogorov, V, et al.
Udgivet: (2010)

Sherali-Adams relaxations for valued CSPs
af: Thapper, J, et al.
Udgivet: (2015)

The Power of Linear Programming for Valued CSPs
af: Thapper, J, et al.
Udgivet: (2012)

The power of linear programming for valued CSPs
af: Thapper, J, et al.
Udgivet: (2015)

The power of linear programming for valued CSPs
af: Thapper, J, et al.
Udgivet: (2012)

Necessary conditions for tractability of valued CSPs
af: Thapper, J, et al.
Udgivet: (2015)

PTAS for sparse general-valued CSPs
af: Mezei, B, et al.
Udgivet: (2023)

Treewidth-pliability and PTAS for Max-CSPs
af: Romero, M, et al.
Udgivet: (2021)

PTAS for sparse general-valued CSPs
af: Mezei, BF, et al.
Udgivet: (2021)

CLAP: A new algorithm for promise CSPs
af: Ciardo, L, et al.
Udgivet: (2023)

The complexity of Boolean surjective general-valued CSPs
af: Fulla, P, et al.
Udgivet: (2017)

The limits of SDP relaxations for general-valued CSPs
af: Thapper, J, et al.
Udgivet: (2018)

The complexity of Boolean surjective general-valued CSPs
af: Fulla, P, et al.
Udgivet: (2017)

The limits of SDP relaxations for general-valued CSPs
af: Thapper, J, et al.
Udgivet: (2017)

The complexity of Boolean surjective general-valued CSPs
af: Fulla, P, et al.
Udgivet: (2018)

The power of Sherali-Adams relaxations for general-valued CSPs
af: Thapper, J, et al.
Udgivet: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
af: Thapper, J, et al.
Udgivet: (2017)

On the combinatorics of sparsification
af: Huang Fenix WD, et al.
Udgivet: (2012-10-01)

On singleton arc consistency for CSPs defined by monotone patterns
af: Carbonnel, C, et al.
Udgivet: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
af: Carbonnel, C, et al.
Udgivet: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
af: Cooper, M, et al.
Udgivet: (2017)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
af: Cooper, M, et al.
Udgivet: (2016)

The complexity of general-valued CSPs seen from the other side
af: Carbonnel, C, et al.
Udgivet: (2018)

Small Promise CSPs that reduce to large CSPs
af: Alexandr Kazda, et al.
Udgivet: (2022-08-01)

Tractable classes of binary CSPs defined by excluded topological minors
af: Cohen, D, et al.
Udgivet: (2015)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
af: Martin C. Cooper, et al.
Udgivet: (2017-12-01)