Epsilon-coresets for clustering (with outliers) in doubling metrics
We study the problem of constructing ε-coresets for the (k, z)-clustering problem in a
doubling metric M (X, d). An ε-coreset is a weighted subset S⊆ X with weight function w: S→ …
doubling metric M (X, d). An ε-coreset is a weighted subset S⊆ X with weight function w: S→ …
Near-linear time approximation schemes for clustering in doubling metrics
V Cohen-Addad, AE Feldmann, D Saulpic - Journal of the ACM (JACM), 2021 - dl.acm.org
We consider the classic Facility Location, k-Median, and k-Means problems in metric spaces
of doubling dimension d. We give nearly linear-time approximation schemes for each …
of doubling dimension d. We give nearly linear-time approximation schemes for each …
Novel properties of hierarchical probabilistic partitions and their algorithmic applications
S Banerjee, Y Bartal, LA Gottlieb… - 2024 IEEE 65th Annual …, 2024 - ieeexplore.ieee.org
We present a refined construction of hierarchical probabilistic partitions with novel
properties, substantially stronger than previously known. Our construction provides a family …
properties, substantially stronger than previously known. Our construction provides a family …
Streaming algorithms for geometric Steiner forest
A Czumaj, SHC Jiang, R Krauthgamer… - ACM Transactions on …, 2024 - dl.acm.org
We consider a generalization of the Steiner tree problem, the Steiner forest problem, in the
Euclidean plane: the input is a multiset, partitioned into color classes. The goal is to find a …
Euclidean plane: the input is a multiset, partitioned into color classes. The goal is to find a …
A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the
prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree …
prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree …
Near-Optimal Dimension Reduction for Facility Location
L Huang, SHC Jiang, R Krauthgamer, D Yue - arXiv preprint arXiv …, 2024 - arxiv.org
Oblivious dimension reduction,\{a} la the Johnson-Lindenstrauss (JL) Lemma, is a
fundamental approach for processing high-dimensional data. We study this approach for …
fundamental approach for processing high-dimensional data. We study this approach for …
Model-Agnostic Approximation of Constrained Forest Problems
C Coupette, A Montaseri, C Lenzen - arXiv preprint arXiv:2407.14536, 2024 - arxiv.org
Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995
capture a wide range of network design problems with edge subsets as solutions, such as …
capture a wide range of network design problems with edge subsets as solutions, such as …
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
Y Bartal, LA Gottlieb - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
We give an algorithm that computes a (1+ є)-approximate Steiner forest in near-linear time n·
2 (1/є) O (ddim 2)(loglog n) 2, where ddim is the doubling dimension of the metric space …
2 (1/є) O (ddim 2)(loglog n) 2, where ddim is the doubling dimension of the metric space …
Approximation Algorithms and Sketches for Clustering
D Saulpic - 2022 - theses.hal.science
This thesis presents contributions to the theoretical study of clustering problems. The broad
objective of these problems is to partition a data set into groups, such that data in the same …
objective of these problems is to partition a data set into groups, such that data in the same …
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
LA Gottlieb, Y Bartal - arXiv preprint arXiv:1904.03611, 2019 - arxiv.org
We give an algorithm that computes a $(1+\epsilon) $-approximate Steiner forest in near-
linear time $ n\cdot 2^{(1/\epsilon)^{O (ddim^ 2)}(\log\log n)^ 2} $. This is a dramatic …
linear time $ n\cdot 2^{(1/\epsilon)^{O (ddim^ 2)}(\log\log n)^ 2} $. This is a dramatic …