Bounding ε-scatter dimension via metric sparsity

Speaker(s)

Marcin Pilipczuk

Language of the talk

English

Date

Nov. 29, 2024, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range of clustering problems in classes of metric spaces that admit a bound on the ε-scatter dimension. Our main result is such a bound for metrics induced by graphs from any fixed proper minor-closed graph class. The bound is double-exponential in ε^{−1} and the Hadwiger number of the graph class and is accompanied by a nearly tight lower bound that holds even in graph classes of bounded treewidth.

On the way to the main result, we introduce metric analogs of well-known graph invariants from the theory of sparsity, including generalized coloring numbers and flatness (aka uniform quasi-wideness), and show bounds for these invariants in proper minor-closed graph classes.

Finally, we show the power of newly introduced toolbox by showing a coreset for k-Center in any proper minor-closed graph class whose size is polynomial in k (but the exponent of the polynomial depends on the graph class and ε^{−1}).

Joint work with Romain Bourneuf, accepted to SODA 2025.

---