On Multiplicative $\lambda$-Approximations and Some Geometric Applications

DOI10.1137/100801809zbMath1281.28006OpenAlexW2047184404MaRDI QIDQ2848204

Ilan Newman, Yuri Rabinovich

Publication date: 25 September 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100801809

zbMATH Keywords

weight functiondimension reductionsparsificationcore setmultiplicative approximation

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Discrete mathematics in relation to computer science (68R99) Classical measure theory (28A99) Combinatorial probability (60C99)

Related Items (8)

Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ Isoperimetric inequalities in simplicial complexes ⋮ Sparsification of Binary CSPs ⋮ Extremal hypercuts and shadows of simplicial complexes ⋮ Ramanujan complexes and high dimensional expanders ⋮ On connectivity of the facet graphs of simplicial complexes ⋮ Sparsification of Binary CSPs ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

This page was built for publication: On Multiplicative $\lambda$-Approximations and Some Geometric Applications