Imagen de Portada

Improved Algorithms for Clustering with Noisy Distance Oracles

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Pradhan, Pinki, Bhattacharya, Anup, Jaiswal, Ragesh
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Improved Sublinear-time Moment Estimation using Weighted Sampling
por: Bhattacharya, Anup, et al.
Publicado: (2025)

Clustering What Matters in Constrained Settings
por: Jaiswal, Ragesh, et al.
Publicado: (2023)

A Quantum Approximation Scheme for k-Means
por: Jaiswal, Ragesh
Publicado: (2023)

Fast $k$-means Seeding Under The Manifold Hypothesis
por: Shah, Poojan, et al.
Publicado: (2026)

Robust-Sorting and Applications to Ulam-Median
por: Jaiswal, Ragesh, et al.
Publicado: (2025)

FPT Approximation for Capacitated Sum of Radii
por: Jaiswal, Ragesh, et al.
Publicado: (2024)

Quantum (Inspired) $D^2$-sampling with Applications
por: Shah, Poojan, et al.
Publicado: (2024)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
por: Shah, Poojan, et al.
Publicado: (2025)

Distribution Testing Meets Sum Estimation
por: Pradhan, Pinki, et al.
Publicado: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
por: Bilò, Davide, et al.
Publicado: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
por: Kuroki, Yuko, et al.
Publicado: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
por: Kadria, Avi, et al.
Publicado: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
por: Manoharan, Vignesh, et al.
Publicado: (2025)

Hamming Distance Oracle
por: Boneh, Itai, et al.
Publicado: (2024)

Distributed Distance Sensitivity Oracles
por: Manoharan, Vignesh, et al.
Publicado: (2024)

Path-Reporting Distance Oracles with Linear Size
por: Neiman, Ofer, et al.
Publicado: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
por: Bilò, Davide, et al.
Publicado: (2023)

Nearly Optimal Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

New Diameter Approximations via Distance Oracle Techniques
por: Kirkpatrick, Yael, et al.
Publicado: (2026)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
por: Neiman, Ofer, et al.
Publicado: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Sublinear Spectral Clustering Oracle with Little Memory
por: Shen, Ranran, et al.
Publicado: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
por: Dey, Dipan, et al.
Publicado: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
por: Kopelowitz, Tsvi, et al.
Publicado: (2023)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
por: Khanna, Sanjeev, et al.
Publicado: (2026)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
por: Horowicz, Noam, et al.
Publicado: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
por: Yan, Shuyi
Publicado: (2025)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
por: Boneh, Itai, et al.
Publicado: (2025)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
por: Braverman, Vladimir, et al.
Publicado: (2025)

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
por: Elkin, Michael, et al.
Publicado: (2023)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
por: Harada, Kaito, et al.
Publicado: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Many Flavors of Edit Distance
por: Bhattacharya, Sudatta, et al.
Publicado: (2024)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
por: Fan, Chenglin, et al.
Publicado: (2025)

Improved Approximation Algorithms for Relational Clustering
por: Esmailpour, Aryan, et al.
Publicado: (2024)

Max-Distance Sparsification for Diversification and Clustering
por: Kumabe, Soh
Publicado: (2024)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
por: Chen, Wenjing, et al.
Publicado: (2023)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
por: Kociumaka, Tomasz, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Chamfer Distance
por: Goranci, Gramoz, et al.
Publicado: (2025)

Improved Algorithms for Distance Selection and Related Problems
por: Wang, Haitao, et al.
Publicado: (2023)